# Strong Exponential Time Hypothesis (SETH)

Revision as of 10:30, 15 February 2023 by Admin (talk | contribs) (Created page with "== 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 == MBETH, ETH == Implied by the following Hypothesis == OVH, [[Unbalanced Orthogonal Vectors Hypothesis (UOVH)|UOVH]...")

## Target Problem

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

## Implied by the following Hypothesis

## Computation Model

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

## Proven?

No

## Year

## References/Citation

Impagliazzo, Paturi, and Zane