Exponential Time Hypothesis
A core assumption in computational complexity theory concerning the complexity of exact algorithms. It asserts that no algorithm for the 3-SAT problem runs in time 2^{o(n)}, providing a fine-grained lower-bound framework for NP-hard problems.
Core Facts
ETH has not been proved or disproved to date, but it has become a cornerstone assumption in fields such as parameterized complexity and exact algorithm design.
The Exponential Time Hypothesis (ETH) was proposed by Impagliazzo and Paturi in 1999.
Timeline (last 90 days)
The complexity group claims a deterministic algorithm that exactly counts the number of satisfying solutions of any conjunctive normal form formula, fast enough to refute the Exponential Time Hypothesis (ETH).
The core assertion of ETH is that no algorithm solves 3-SAT in subexponential time, specifically in the form 2^Ω(n).
SETH is stronger than ETH: ETH only requires that 3-SAT has no 2^{o(n)} algorithm, whereas SETH gives finer exponential lower bounds for general k-SAT.
If ETH is disproven, SETH naturally does not hold; but the converse does not hold—disproving SETH does not necessarily refute ETH.
If ETH holds, then no O(n^{2-ε}) algorithm exists for the edit distance problem; if SETH holds, problems such as dynamic time warping also have similar lower bounds.
There are mainly two ways to disprove ETH: one is to construct a concrete subexponential algorithm; the other is to prove through some non-constructive argument that such an algorithm must exist.
The Exponential Time Hypothesis (ETH) was proposed by Impagliazzo and Paturi in 1999.
The basic form of ETH asserts that for the 3-SAT problem, any algorithm has a worst-case time complexity of at least 2^{δn}, where n is the number of variables and δ is some positive constant.
ETH has not been proved or disproved to date, but it has become a cornerstone assumption in fields such as parameterized complexity and exact algorithm design.
The model's results on the Kakeya conjecture, ETH and QCD are currently still at the stage of requiring external verification.
1 more timeline events
All Facts (11)
ETH has not been proved or disproved to date, but it has become a cornerstone assumption in fields such as parameterized complexity and exact algorithm design.
75%Partially VerifiedThe Exponential Time Hypothesis (ETH) was proposed by Impagliazzo and Paturi in 1999.
75%UnverifiedThe complexity group claims a deterministic algorithm that exactly counts the number of satisfying solutions of any conjunctive normal form formula, fast enough to refute the Exponential Time Hypothesis (ETH).
50%UnverifiedThe core assertion of ETH is that no algorithm solves 3-SAT in subexponential time, specifically in the form 2^Ω(n).
50%UnverifiedIf ETH is disproven, SETH naturally does not hold; but the converse does not hold—disproving SETH does not necessarily refute ETH.
50%UnverifiedIf ETH holds, then no O(n^{2-ε}) algorithm exists for the edit distance problem; if SETH holds, problems such as dynamic time warping also have similar lower bounds.
50%UnverifiedThere are mainly two ways to disprove ETH: one is to construct a concrete subexponential algorithm; the other is to prove through some non-constructive argument that such an algorithm must exist.
50%UnverifiedSETH is stronger than ETH: ETH only requires that 3-SAT has no 2^{o(n)} algorithm, whereas SETH gives finer exponential lower bounds for general k-SAT.
50%UnverifiedThe model's results on the Kakeya conjecture, ETH and QCD are currently still at the stage of requiring external verification.
50%UnverifiedThe basic form of ETH asserts that for the 3-SAT problem, any algorithm has a worst-case time complexity of at least 2^{δn}, where n is the number of variables and δ is some positive constant.
50%UnverifiedOpenAI recently shared its model's results on the Kakeya conjecture, the Exponential Time Hypothesis (ETH) and quantum chromodynamics (QCD).
50%