# P3140: Strong Exponential Time Hypothesis

- ID: `P3140`
- Reference: `strong-exponential-time-hypothesis`
- Page: https://theoremdb.org/statements/P3140
- Record maturity: Reviewed problem with recorded work

## Problem

For every \(\varepsilon>0\), does there exist \(k\ge3\) such that \(k\)-SAT on \(n\) variables cannot be decided in time \(O((2-\varepsilon)^n)\) by a deterministic algorithm?

### Context

Known frontier: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence.

Open boundary: The unrestricted quantified lower bound remains unproved and undisproved.

### Problem setup

- **Definition (k-SAT).** Satisfiability of a CNF formula with at most k literals per clause.
- **Definition (deterministic running time).** Worst-case time as a function of the number n of variables, with polynomial factors absorbed.
- **Remark.** SETH says the base of the best exponential-time SAT algorithm approaches 2 as clause width grows. It is a precise hypothesis used to derive conditional lower bounds across algorithms.

### What counts as a solution

- Prove the quantified lower bound in a standard deterministic machine model.
- Or give one ε>0 and algorithms solving k-SAT in O((2−ε)^n) for every k.

## Status

OPEN as checked on 2026-08-01. Strongest checked neighboring result: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence. Exact unresolved remainder: The unrestricted quantified lower bound remains unproved and undisproved. [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (Current status and exact unresolved remainder).** OPEN as checked on 2026-08-01. Strongest checked neighboring result: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence. Exact unresolved remainder: The unrestricted quantified lower bound remains unproved and undisproved.

The problem was checked as open on 2026-08-01.

The strongest neighboring result found in the cited sources is: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence.

The exact unresolved remainder is: The unrestricted quantified lower bound remains unproved and undisproved.

A complete resolution must meet the following acceptance conditions:
- Prove the quantified lower bound in a standard deterministic machine model.
- Or give one ε>0 and algorithms solving k-SAT in O((2−ε)^n) for every k.

### Background and intake notes

- Original intake status: OPEN as checked on 2026-08-01. Strongest checked neighboring result: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence. Exact unresolved remainder: The unrestricted quantified lower bound remains unproved and undisproved.
- The release review checked 2 structured sources on 2026-08-01.
- Equivalent-formulation queries: Strong Exponential Time Hypothesis open 2026; SETH k-SAT base 2 current algorithms
- Strongest checked neighboring result: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence.
- Exact unresolved remainder: The unrestricted quantified lower bound remains unproved and undisproved.

### Other known results

- **Claim 2** (supported): Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence. [1](#reference-1) [2](#reference-2)

### Prior approaches

- **Route 1** (supported): The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence. Unresolved remainder: The unrestricted quantified lower bound remains unproved and undisproved. [1](#reference-1) [2](#reference-2)

### Open directions

- **Route 2** (reported): The unrestricted quantified lower bound remains unproved and undisproved.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `strong-exponential-time-hypothesis`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Russell Impagliazzo and Ramamohan Paturi, “On the Complexity of k-SAT”. Journal of Computer and System Sciences 62(2) (2001), 367-375. DOI 10.1006/jcss.2000.1727. definition and consequences https://doi.org/10.1006/jcss.2000.1727
   - Also cited at R. Impagliazzo and R. Paturi, On the complexity of k-SAT, Journal of Computer and System Sciences 62 (2001). definition and consequences
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - Introduces the exponential-time hypothesis framework and the limiting k-SAT constant.
   - Source used to assess the problem's recorded status.
   - For Strong Exponential Time Hypothesis: This is the dated publication status for the canonical target Strong Exponential Time Hypothesis.
   - Source named by the research packet.
2. <a id="reference-2"></a>Russell Impagliazzo, Ramamohan Paturi, and Francis Zane, “Which Problems Have Strongly Exponential Complexity?”. Journal of Computer and System Sciences 63(4) (2001), 512-530. DOI 10.1006/jcss.2001.1774. sparsification lemma and consequences https://doi.org/10.1006/jcss.2001.1774
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - Supplies the sparsification machinery underlying the modern SETH formulation.
   - Source used to assess the problem's recorded status.
   - For Strong Exponential Time Hypothesis: Supplies the sparsification machinery underlying the modern SETH formulation.