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

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?

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 $2^n poly(n)$ , alors par Ryan L'article de Williams montre que $NEXP \not\subseteq P/poly$ .