Folgen subexponentieller Beweise / Algorithmen für SAT

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?

cc.complexity-theory sat proof-complexity Opt
quelle

Dies würde die exponentielle Zeithypothese widerlegen, die verschiedene Konsequenzen hat (siehe Wikipedia-Artikel).

Artem Kaznatcheev

@ArtemKaznatcheev Kommentar -> Antwort?

Suresh Venkat

@ 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

Wenn die Antwort richtig ist, ist es egal, wer sie gibt :)

Suresh Venkat

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:

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

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

Artem Kaznatcheev
quelle

Ich denke, dass der erste Absatz Ihrer Antwort nur die Definition der Exponentialzeithypothese ist.

Tsuyoshi Ito