Would there be any major consequences if SAT had at most subexponential unsat proofs or even more strongly, SAT had subexponential-time algorithms?
5
-
4$\begingroup$ It would disprove the exponential time hypothesis which has various consequences (covered in the wikipedia article). $\endgroup$– Artem Kaznatcheev ♦Dec 2, 2011 at 3:20
-
1$\begingroup$ @ArtemKaznatcheev comment -> answer ? $\endgroup$– Suresh VenkatDec 2, 2011 at 3:34
-
1$\begingroup$ @SureshVenkat feels kind of awkward to give an answer when Ryan Williams can provide a much better one. I gave one for now, but I hope Ryan and others pitch in with something cooler. $\endgroup$– Artem Kaznatcheev ♦Dec 2, 2011 at 4:05
-
7$\begingroup$ If the answer is correct, it doesn't matter who gives it :) $\endgroup$– Suresh VenkatDec 2, 2011 at 6:00
-
7$\begingroup$ Sorry Artem, my answer wouldn't be much cooler than yours... I guess one thing to add would be that ETH is false implies new superlinear circuit lower bounds (same paper). $\endgroup$– Ryan WilliamsDec 3, 2011 at 3:39
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
If SAT had a subexponential-time algorithm, the you would disprove the exponential time hypothesis.
For fun consequences: if you showed that circuit SAT over AND,OR,NOT with $n$ variables and $poly(n)$ circuit gates can be solved faster than the trivial $2^n poly(n)$ approach, then by Ryan Williams' paper you show that $NEXP \not\subseteq P/poly$.
answered Dec 2, 2011 at 4:03
-
10$\begingroup$ I think that the first paragraph of your answer is just the definition of the exponential time hypothesis. $\endgroup$ Dec 3, 2011 at 0:32