Folgen subexponentieller Beweise / Algorithmen für SAT

14

Gibt es größere Konsequenzen, wenn SAT höchstens subexponentielle Beweise für unsat hätte oder noch stärker, wenn SAT Algorithmen für subexponentielle Zeit hätte?

Opt
quelle
4
Dies würde die exponentielle Zeithypothese widerlegen, die verschiedene Konsequenzen hat (siehe Wikipedia-Artikel).
Artem Kaznatcheev
1
@ArtemKaznatcheev Kommentar -> Antwort?
Suresh Venkat
1
@ SureshVenkat fühlt sich irgendwie peinlich, eine Antwort zu geben, wenn Ryan Williams eine viel bessere liefern kann. Ich habe vorerst eine gegeben, aber ich hoffe, dass Ryan und andere sich mit etwas Coolerem einbringen.
Artem Kaznatcheev
7
Wenn die Antwort richtig ist, ist es egal, wer sie gibt :)
Suresh Venkat
7
Entschuldigung Artem, meine Antwort wäre nicht viel cooler als deine ... Ich denke, eine Sache, die hinzugefügt werden müsste, wäre, dass ETH falsch ist und neue untere Schranken für superlineare Schaltkreise impliziert (dasselbe Papier).
Ryan Williams

Antworten:

20

Wenn SAT einen subexponentiellen Zeitalgorithmus hätte, würden Sie die exponentielle Zeithypothese widerlegen .

npÖly(n)2npÖly(n)NEXPP/pÖly

Artem Kaznatcheev
quelle
10
Ich denke, dass der erste Absatz Ihrer Antwort nur die Definition der Exponentialzeithypothese ist.
Tsuyoshi Ito