More Believable Exponential Time Hypothesis (MBETH)
Jump to navigation
Jump to search
Target Problem
Description
There exists a $k \geq 3$ and a $\delta > 0$ so that $k$-SAT on $n$ variables cannot be solved in $O(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
https://people-csail-mit-edu.ezproxy.canberra.edu.au/virgi/6.s078/lect2.pdf