Exponential Time Hypothesis (ETH)
Jump to navigation
Jump to search
Target Problem
Description
There is some constant $\delta > 0$ such that CNF-SAT requires $\Omega(2^{\delta n})$.
Implies the following Hypothesis
Implied by the following Hypothesis
Computation Model
Word-RAM on $\log(n)$ bit words
Proven?
No
Year
References/Citation
http://people.csail.mit.edu.ezproxy.canberra.edu.au/virgi/eccentri.pdf Page 5