Editing Time complexity (section)

==== Exponential time hypothesis ====
{{Main|Exponential time hypothesis}}

The '''exponential time hypothesis''' ('''ETH''') is that [[3SAT]], the satisfiability problem of Boolean formulas in [[conjunctive normal form]] with at most three literals per clause and with ''n'' variables, cannot be solved in time 2<sup>''o''(''n'')</sup>. More precisely, the hypothesis is that there is some absolute constant {{math|''c'' > 0}} such that 3SAT cannot be decided in time 2<sup>''cn''</sup> by any deterministic Turing machine. With ''m'' denoting the number of clauses, ETH is equivalent to the hypothesis that ''k''SAT cannot be solved in time 2<sup>''o''(''m'')</sup> for any integer {{math|''k'' ≥ 3}}.<ref>{{Cite journal|first1=R.|last1=Impagliazzo|author1-link=Russell Impagliazzo|first2=R.|last2=Paturi|first3=F.|last3=Zane|title=Which problems have strongly exponential complexity?|journal=[[Journal of Computer and System Sciences]]|volume=63|issue=4|year=2001|pages=512–530|doi=10.1006/jcss.2001.1774|doi-access=free}}</ref> The exponential time hypothesis implies [[P ≠ NP]].