Exponential time hypothesis

In computational complexity theory, the exponential time hypothesis or ETH is an unproven computational hardness assumption that was formulated by Impagliazzo & Paturi (1999). It states that satisfiability of 3-CNF Boolean formulas (3-SAT) cannot be solved in subexponential time, 2 o ( n ) {\displaystyle 2^{o(n)}} .