Exponential time hypothesis

In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by Impagliazzo & Paturi (1999). It states that satisfiability of 3-CNF Boolean formulas cannot be solved in subexponential time, ${\displaystyle 2^{o(n)}}$. More precisely, the usual form of the hypothesis asserts the existence of a number ${\displaystyle s_{3}>0}$ such that all algorithms that correctly solve this problem require time at least ${\displaystyle 2^{s_{3}n}.}$ The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement. It implies that many computational problems are equivalent in complexity, in the sense that if one of them has a subexponential time algorithm then they all do, and that many known algorithms for these problems have optimal or near-optimal time complexity.^[1]