Strong Exponential Time Hypothesis
A strengthened version of the Exponential Time Hypothesis asserting that the lower bound on solving time for k-SAT approaches 2^n as k increases, meaning it cannot be significantly faster than brute-force enumeration. It underlies many core conjectures in fine-grained complexity.
Timeline (last 90 days)
The Strong Exponential Time Hypothesis (SETH) was proposed by Impagliazzo, Paturi and Zane in 2001.
SETH asserts that for any δ<1, there exists a sufficiently large k such that k-SAT cannot be solved in O(2^{δn}) time.
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.
All Facts (5)
The Strong Exponential Time Hypothesis (SETH) was proposed by Impagliazzo, Paturi and Zane in 2001.
50%UnverifiedSETH asserts that for any δ<1, there exists a sufficiently large k such that k-SAT cannot be solved in O(2^{δn}) time.
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%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%