Consequências de provas / algoritmos subexponenciais para SAT

Haveria grandes consequências se o SAT tivesse no máximo provas subexponenciais de insat ou ainda mais fortemente, o SAT tivesse algoritmos de tempo subexponencial?

cc.complexity-theory sat proof-complexity Optar
fonte

Isso refutaria a hipótese do tempo exponencial que tem várias consequências (abordadas no artigo da Wikipedia).

Artem Kaznatcheev

@ArtemKaznatcheev comentário -> resposta?

Suresh Venkat

O @SureshVenkat parece meio estranho dar uma resposta quando Ryan Williams pode oferecer uma resposta muito melhor. Eu dei um por enquanto, mas espero que Ryan e outros participem com algo mais legal.

Artem Kaznatcheev

Se a resposta for correta, não importa que lhe dá :)

Suresh Venkat

Desculpe Artem, minha resposta não seria muito mais legal que a sua ... Acho que uma coisa a acrescentar seria que o ETH é falso implica em novos limites inferiores do circuito superlinear (mesmo documento).

Ryan Williams

Respostas:

Se o SAT tivesse um algoritmo de tempo subexponencial, você contestaria a hipótese de tempo exponencial .

$n$ $poly(n)$ $2^n poly(n)$ $NEXP \not\subseteq P/poly$

Artem Kaznatcheev
fonte

Penso que o primeiro parágrafo da sua resposta é apenas a definição da hipótese do tempo exponencial.

Tsuyoshi Ito