Exponential time hypothesis

{{short description|Unproven computational hardness assumption}}

{{short description|Unproven computational hardness assumption}}

In [[computational complexity theory]], the '''exponential time hypothesis''' or '''ETH''' is an unproven [[computational hardness assumption]] that was formulated by {{harvtxt|Impagliazzo|Paturi|1999}}. It states that [[3-SAT|satisfiability of 3-CNF Boolean formulas]] (3-SAT) cannot be solved in [[subexponential time]], <math>2^{o(n)}</math>. More precisely, the usual form of the hypothesis asserts the existence of a number <math>s_3 > 0</math> such that all algorithms that correctly solve 3-SAT require time at least <math>2^{s_3 n}.</math> The exponential time hypothesis, if true, would imply that [[P versus NP problem|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 {{nowrap|complexity.{{r|ip99}}}}

In [[computational complexity theory]], the '''exponential time hypothesis''' or '''ETH''' is an unproven [[computational hardness assumption]] that was formulated by {{harvtxt|Impagliazzo|Paturi|1999}}. It states that [[3-SAT|satisfiability of 3-CNF Boolean formulas]] (3-SAT) cannot be solved in [[subexponential time]], <math>2^{o(n)}</math>. More precisely, the usual form of the hypothesis asserts the existence of a number <math>s_3 > 0</math> such that all algorithms that correctly solve 3-SAT require time at least <math>2^{s_3 n}.</math> The exponential time hypothesis, if true, would imply that [[P versus NP problem|P ≠ NP]], but it is a stronger statement. Beyond NP, it implies that many known algorithms (including those with lower than exponential time) have optimal or near-optimal time {{nowrap|complexity.{{r|ip99}}}}

==Definition==

==Definition==