Strong Exponential Time Hypothesis (SETH)
Jump to navigation
Jump to search
Target Problem
Description
For every $\epsilon > 0$, there exists an integer $k \geq 3$ such that $k$-SAT cannot be solved in $O(2^{(1-\epsilon) n})$ time.
Implies the following Hypothesis
Implied by the following Hypothesis
Computation Model
Word-RAM on $\log(n)$ bit words
Proven?
No
Year
References/Citation
Impagliazzo, Paturi, and Zane