Draft:Strong Exponential Time Hypothesis

• Comment: Is there any reason why this needs to be a separate article, given it is already covered at Exponential time hypothesis? Devonian Wombat (talk) 12:58, 15 May 2026 (UTC)

• Comment: In accordance with Wikipedia's Conflict of interest guideline, I disclose that I have a conflict of interest regarding the subject of this article. EricNohara (talk) 05:26, 23 April 2026 (UTC)

---

In computational complexity theory, the Strong Exponential Time Hypothesis (SETH) is a conjecture relating to the time complexity of solving the Boolean satisfiability problem (SAT). Informally, SETH conjectures that there does not exist an algorithm to solve all instances of SAT significantly faster than a brute force solution in the worst case. SETH is used throughout fine-grained complexity theory to establish conditional lower bounds for a wide array of problems through fine grained reductions.

k-SAT

The k-satisfiability problem ($k{\text{-SAT}}$) is a restricted version of SAT where the input formula is in conjunctive normal form (CNF) and each clause contains at most $k$ literals

A CNF formula is a conjunction of clauses:

$\varphi =C_{1}\land C_{2}\land \dots \land C_{m}$,

where each clause $C_{i}$ is a disjunction of literals and has the form:

$C_{i}=\ell _{1}^{i}\lor \ell _{2}^{i}\lor \dots \lor \ell _{r_{i}}^{i},\quad r_{i}\leq k$.

The goal of $k{\text{-SAT}}$ is to determine whether there exists an assignment to the variables that satisfies all clauses. In other words, $k{\text{-SAT}}$ returns true if there exists an assignment such that $\varphi =1$.

k-SAT Example

Bipartite visualization of the k-SAT example

Consider the following ${\text{k-SAT}}$ formula where $k=3$:

$\varphi =(x_{1}\lor \lnot x_{2}\lor x_{3})\land (\lnot x_{1}\lor x_{2}\lor x_{4})\land (x_{2}\lor \lnot x_{3})$.

$k{\text{-SAT}}$ asks whether there exists an assignment to the variables $x_{1},x_{2},x_{3},x_{4}$ such that $\varphi =1$.

Consider the assignment:

$x_{1}=1,\quad x_{2}=1,\quad x_{3}=0,\quad x_{4}=1$.

Under this assignment:

• $(x_{1}\lor \lnot x_{2}\lor x_{3})=(1\lor 0\lor 0)=1$
• $(\lnot x_{1}\lor x_{2}\lor x_{4})=(0\lor 1\lor 1)=1$
• $(x_{2}\lor \lnot x_{3})=(1\lor 1)=1$

Since all clauses are satisfied, $\varphi =1$. Therefore, the solution to this example is true.

k-SAT Exhaustive Search

k-SAT Algorithms

There have been a variety of algorithms developed to solve the $k{\text{-}}SAT$ problem, with their performance depending on the value of $k$ and the structure of the input formula.

Exhaustive search is a straightforward approach to solving $k{\text{-}}SAT$ which evaluates all $2^{n}$ possible variable assignments. This approach has a running time of $O(2^{n})$.

Algorithms more efficient than exhaustive search have been developed that improve the exponent base of the runtime. Below is a list of the best known algorithms for different values of $k$.

Best Known Algorithms for Different Values of $k$

Problem	Runtime	Type	Algorithm
$3{\text{-}}SAT$	$O(1.334^{n})$	Probabilistic	Schöning
$4{\text{-}}SAT$	$O(1.476^{n})$	Probabilistic	PPSZ (Paturi, Pudlák, Saks, Zane)
$5{\text{-}}SAT$	$O(1.569^{n})$	Probabilistic	PPSZ
$6{\text{-}}SAT$	$O(1.637^{n})$	Probabilistic	PPSZ
Generalized $k{\text{-}}SAT$	$O{\Big (}(2-{\frac {2}{k}})^{n}{\Big )}$	Probabilistic	Schöning

Despite these advances, note that there does not exists an algorithm that runs in sub exponential time. SETH conjectures that for all $k$, these improvements cannot reduce the exponent below $2^{n}$ by more than a sub constant factor.

SETH Formal Definition

SETH Runtime Visualization

Formally, SETH states that for every $\epsilon >0$, there exists some integer $k\geq 3$ such that $k{\text{-}}SAT$ on $n$ variables and $m$ clauses cannot be solved in $O(2^{(1-\epsilon )n})$ time.

Intuition

SETH is a strengthened version of the Exponential Time Hypothesis (ETH). ETH states that $3{\text{-}}SAT$ requires $2^{\delta n}$ time to solve, for some constant $\delta >0$. In other words, it states that $3{\text{-}}SAT$ cannot be solved in sub-exponential time. However, SETH strengthens this claim by stating that for larger values of $k$, $k{\text{-}}SAT$ still cannot be solved significantly faster than an exhaustive search over all assignments, with a running time of $O(2^{n})$.

Role in Fine-Grained Complexity

SETH is used throughout fine-grained complexity theory to establish conditional lower bounds for various computational problems. Rather than proving unconditional hardness, many problems show that a significantly faster algorithm for them would imply a faster algorithm for $k{\text{-}}SAT$, thereby contradicting SETH. However, this hardness is conditioned on SETH being true.

These results are usually obtained through reductions from $k{\text{-}}SAT$ or related problems such as the Orthogonal Vectors (OV) problem. Thus, SETH provides a framework in fine-grained complexity theory for transferring hardness from satisfiability problems to a wide range of other domains such as string algorithms, graph algorithms, and dynamic data structures.