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

1 Answer 1

21
$\begingroup$

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$.

$\endgroup$
1
  • 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

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.