<p>If SAT had a subexponential-time algorithm, the you would disprove the <a href="http://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="nofollow noreferrer">exponential time hypothesis</a>. </p>

<p>For fun consequences: if you showed that circuit SAT over AND,OR,NOT with <span class="math-container">$n$</span> variables and <span class="math-container">$poly(n)$</span> circuit gates can be solved faster than the trivial <span class="math-container">$2^n poly(n)$</span> approach, then by <a href="http://www.cs.cmu.edu/~ryanw/improved-algs-lbs2.pdf" rel="nofollow noreferrer">Ryan Williams' paper</a> you show that <span class="math-container">$NEXP \not\subseteq P/poly$</span>.</p>

CC BY-SA 3.0
2011-12-03T00:32:55.453Z
I think that the first paragraph of your answer is just the definition of the exponential time hypothesis.
Tsuyoshi Ito
CC BY-SA 4.0
2011-12-02T04:03:22.210Z
2019-11-10T19:19:58.700Z
2019-11-10T19:19:58.700Z
Artem Kaznatcheev
<p>Would there be any major consequences if SAT had at most subexponential unsat proofs or even more strongly, SAT had subexponential-time algorithms?</p>

CC BY-SA 3.0
2011-12-02T03:20:49.770Z
It would disprove the [exponential time hypothesis](http://en.wikipedia.org/wiki/Exponential_time_hypothesis) which has various consequences (covered in the wikipedia article).
Artem Kaznatcheev
CC BY-SA 3.0
2011-12-02T03:34:29.710Z
@ArtemKaznatcheev comment -> answer ?
Suresh Venkat
CC BY-SA 3.0
2011-12-02T04:05:28.947Z
@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.
Artem Kaznatcheev
CC BY-SA 3.0
2011-12-02T06:00:17.497Z
If the answer is correct, it doesn't matter who gives it :)
Suresh Venkat
CC BY-SA 3.0
2011-12-03T03:39:22.837Z
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).
Ryan Williams
<cc.complexity-theory><sat><proof-complexity>
Consequences of sub-exponential proofs/algorithms for SAT
Opt
# Consequences of sub-exponential proofs/algorithms for SAT

(Asked by: username_0 on 2011-12-02)

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

**Tags:** cc.complexity-theory, sat, proof-complexity

> **Comments:**
> **username_1**: It would disprove the [exponential time hypothesis](http://en.wikipedia.org/wiki/Exponential_time_hypothesis) which has various consequences (covered in the wikipedia article).  
> **username_2**: @ArtemKaznatcheev comment -> answer ?  
> **username_1**: @SureshVenkat feels kind of awkward to give an answer when username_3 can provide a much better one. I gave one for now, but I hope Ryan and others pitch in with something cooler.  
> **username_2**: If the answer is correct, it doesn't matter who gives it :)  
> **username_3**: 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).  

---

## 1 answers

### Answer by username_1 on 2011-12-02. Score: 21 | Accepted answer

If SAT had a subexponential-time algorithm, the you would disprove the [exponential time hypothesis](http://en.wikipedia.org/wiki/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 [username_3' paper](http://www.cs.cmu.edu/~ryanw/improved-algs-lbs2.pdf) you show that $NEXP \not\subseteq P/poly$.

> **Comments:**
> **username_4**: I think that the first paragraph of your answer is just the definition of the exponential time hypothesis.  

---

