Exponential time hypothesis

In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, the exponential time hypothesis or ETH is an unproven <a href="/facts/Computational_hardness_assumption/ewjpb1I7">computational hardness assumption</a> that was formulated by Impagliazzo & Paturi (1999). It states that <a href="/facts/3-SAT/wBVRjWoy">satisfiability of 3-CNF Boolean formulas</a> (3-SAT) cannot be solved in <a href="/facts/Subexponential_time/77T62gmf">subexponential time</a>, 
 
 
 
 
 2
 
 o
 (
 n
 )
 
 
 
 
 {\displaystyle 2^{o(n)}}
 
. More precisely, the usual form of the hypothesis asserts the existence of a number 
 
 
 
 
 s
 
 3
 
 
 >
 0
 
 
 {\displaystyle s_{3}>0}
 
 such that all algorithms that correctly solve 3-SAT require time at least 
 
 
 
 
 2
 
 
 s
 
 3
 
 
 n
 
 
 .
 
 
 {\displaystyle 2^{s_{3}n}.}
 
 The exponential time hypothesis, if true, would imply that <a href="/facts/P_versus_NP_problem/xoC7Ruda">P ≠ NP</a>, but it is a stronger statement, since superpolynomial subexponential functions exist, such as 2√n.
Many computational problems are equivalent in complexity, in the sense that if one of them has a subexponential time algorithm then they all do. The exponential time hypothesis implies that many known algorithms for these problems have optimal or near-optimal time complexity.

Exponential time hypothesis open-in-new

Exponential time hypothesis