12
$\begingroup$

Would there be any major consequences if SAT had at most subexponential unsat proofs or even more strongly, SAT had subexponential-time algorithms?

$\endgroup$
  • 4
    $\begingroup$ It would disprove the exponential time hypothesis which has various consequences (covered in the wikipedia article). $\endgroup$ – Artem Kaznatcheev Dec 2 '11 at 3:20
  • 1
    $\begingroup$ @ArtemKaznatcheev comment -> answer ? $\endgroup$ – Suresh Venkat Dec 2 '11 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 '11 at 4:05
  • 6
    $\begingroup$ If the answer is correct, it doesn't matter who gives it :) $\endgroup$ – Suresh Venkat Dec 2 '11 at 6:00
  • 6
    $\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 Williams Dec 3 '11 at 3:39
19
$\begingroup$

If SAT had a subexpoential-time algorithm, the you would disprove the exponential time hypothesis.

For fun cosequences: 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$.

$\endgroup$
  • 10
    $\begingroup$ I think that the first paragraph of your answer is just the definition of the exponential time hypothesis. $\endgroup$ – Tsuyoshi Ito Dec 3 '11 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.