Exponential Time Hypothesis (ETH)

From Algorithm Wiki
Jump to navigation Jump to search

Target Problem

3SAT

Description

There is some constant $\delta > 0$ such that CNF-SAT requires $\Omega(2^{\delta n})$.

Implies the following Hypothesis

MBETH

Implied by the following Hypothesis

SETH, MBETH

Computation Model

Word-RAM on $\log(n)$ bit words

Proven?

No

Year

References/Citation

http://people.csail.mit.edu/virgi/eccentri.pdf Page 5

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Exponential_Time_Hypothesis_(ETH)&oldid=44331"