Nondeterministic Strong Exponential Time Hypothesis (NSETH)
Jump to navigation
Jump to search
Target Problem
[[]]
Description
Refuting unsatisfiable $k$-CNF formulas on $n$ variables requires nondeterministic $2^{n-o(n)}$ time for unbounded $k$.
Implies the following Hypothesis
Implied by the following Hypothesis
Computation Model
Proven?
No (Variants have been disproved)
Year
References/Citation
http://people.csail.mit.edu/virgi/eccentri.pdf Hypothesis 10