3 ms·
The article clearly states this, but the title doesn't, so N.B.: the proof is conditional on exponential time hypothesis, that SAT requires exponential time. Of
by sanxiyn 11y ago
The article clearly states this, but the title doesn't, so N.B.: the proof is conditional on exponential time hypothesis, that SAT requires exponential time. Of course we don't know whether it does.
- paulfr 11y agoWhat the article doesn't state clearly is that this assumes the strong exponential time hypothesis: it assumes that SAT cannot be solved in time 1.9999^n -- in other words that it's impossible to do better than the brute-force algorithm, which has complexity 2^n (up to polynomial factors). That's a very strong assumption.