Consecuencias de las pruebas / algoritmos sub-exponenciales para SAT

¿Habría alguna consecuencia importante si SAT tuviera a lo sumo pruebas subexponenciales no firmes o, aún más fuerte, SAT tuviera algoritmos de tiempo subexponencial?

cc.complexity-theory sat proof-complexity Optar
fuente

Sería refutar la hipótesis del tiempo exponencial que tiene varias consecuencias (cubiertas en el artículo de Wikipedia).

Artem Kaznatcheev

@ArtemKaznatcheev comentario -> respuesta?

Suresh Venkat

@SureshVenkat se siente un poco incómodo al dar una respuesta cuando Ryan Williams puede proporcionar una respuesta mucho mejor. Le di uno por ahora, pero espero que Ryan y otros contribuyan con algo más genial.

Artem Kaznatcheev

Si la respuesta es correcta, no importa quién la dé :)

Suresh Venkat

Lo siento, Artem, mi respuesta no sería mucho mejor que la tuya ... Supongo que una cosa para agregar sería que ETH es falso implica nuevos límites inferiores del circuito superlineal (mismo documento).

Ryan Williams, el

Respuestas:

Si SAT tuviera un algoritmo de tiempo subexponencial, usted refutaría la hipótesis del tiempo exponencial .

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

Artem Kaznatcheev
fuente

Creo que el primer párrafo de su respuesta es solo la definición de la hipótesis del tiempo exponencial.

Tsuyoshi Ito