Conséquences des preuves / algorithmes sous-exponentiels pour SAT

14

Y aurait-il des conséquences majeures si SAT avait tout au plus des preuves non-exponentielles sous-exponentielles ou encore plus fortement, SAT avait des algorithmes de temps sous-exponentiels?

Opter
la source
4
Cela réfuterait l' hypothèse du temps exponentiel qui a diverses conséquences (couvert dans l'article de wikipedia).
Artem Kaznatcheev
1
@ArtemKaznatcheev comment -> répondre?
Suresh Venkat
1
@SureshVenkat se sent un peu gêné de donner une réponse quand Ryan Williams peut fournir une bien meilleure réponse. J'en ai donné un pour le moment, mais j'espère que Ryan et les autres feront quelque chose de plus cool.
Artem Kaznatcheev
7
Si la réponse est correcte, peu importe qui la donne :)
Suresh Venkat
7
Désolé Artem, ma réponse ne serait pas beaucoup plus cool que la vôtre ... Je suppose qu'une chose à ajouter serait que ETH est faux implique de nouvelles limites inférieures de circuit superlinear (même papier).
Ryan Williams

Réponses:

21

Si SAT avait un algorithme de temps sous-exponentiel, vous réfuteriez l' hypothèse de temps exponentiel .

Pour des conséquences amusantes: si vous avez montré que le circuit SAT sur AND, OR, NOT avec n variables et poly(n) les portes de circuit peuvent être résolus plus rapidement que l' approche triviale de 2npoly(n) , alors par Ryan L'article de Williams montre que NEXPP/poly .

Artem Kaznatcheev
la source
10
Je pense que le premier paragraphe de votre réponse n'est que la définition de l'hypothèse de temps exponentielle.
Tsuyoshi Ito