Konsekwencje sub wykładniczych dowodów / algorytmów dla SAT

Czy byłyby jakieś poważne konsekwencje, gdyby SAT miał co najwyżej podwykładnicze dowody niesatysfakcjonujące, a jeszcze silniej, SAT miałby algorytmy podwykładniczego czasu?

cc.complexity-theory sat proof-complexity Optować
źródło

Obaliłoby to wykładniczą hipotezę czasową, która ma różne konsekwencje (opisane w artykule na Wikipedii).

Artem Kaznatcheev

@ArtemKaznatcheev komentarz -> odpowiedź?

Suresh Venkat,

@SureshVenkat czuje się dziwnie, dając odpowiedź, gdy Ryan Williams może udzielić znacznie lepszej odpowiedzi. Na razie dałem jeden, ale mam nadzieję, że Ryan i inni przybędą z czymś fajniejszym.

Artem Kaznatcheev

Jeśli odpowiedź jest prawidłowa, nie ma znaczenia, kto ją podaje :)

Suresh Venkat

Przepraszam, Artemie, moja odpowiedź nie byłaby o wiele fajniejsza niż twoja ... Myślę, że jedną rzeczą do dodania byłoby to, że ETH jest fałszywe, implikuje nowe dolne granice obwodu superliniowego (ten sam papier).

Ryan Williams,

Odpowiedzi:

Gdyby SAT miał algorytm podwykładniczy, obaliłbyś hipotezę o wykładniczym czasie .

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

Artem Kaznatcheev
źródło

Myślę, że pierwszy akapit twojej odpowiedzi to tylko definicja wykładniczej hipotezy czasowej.

Tsuyoshi Ito,