View source for Strong Exponential Time Hypothesis (SETH)

== Target Problem == 

[[k-SAT]]

== 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 == 

[[More Believable Exponential Time Hypothesis (MBETH)|MBETH]], [[Exponential Time Hypothesis (ETH)|ETH]]

== Implied by the following Hypothesis == 

[[Orthogonal Vectors Hypothesis (OVH)|OVH]], [[Unbalanced Orthogonal Vectors Hypothesis (UOVH)|UOVH]]

== Computation Model == 

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

== Proven? == 

No

== Year == 



== References/Citation == 

Impagliazzo, Paturi, and Zane