Lax489179.SETH
The Strong Exponential Time Hypothesis (SETH)
concepts/Lax489179/SETH.lean · lax-489179
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
Definition
For every , there is a width such that -CNF satisfiability has no deterministic algorithm. The width may depend on . This is the exponential-rate formulation of SETH; it expresses the absence of a fixed improvement below base two across all fixed clause widths, even when each width has its own algorithm.
excludes bounded-error randomized algorithms instead. The polynomial factor in the full formula length is explicit in . These are propositions, not axioms.
Lean source view on GitHub
| 1 | import Lax489179.SATTime |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: The Strong Exponential Time Hypothesis (SETH) |
| 6 | type: definition |
| 7 | --- |
| 8 | For every , there is a width such that |
| 9 | -CNF satisfiability has no deterministic |
| 10 | algorithm. The width may depend on |
| 11 | . This is the exponential-rate formulation of SETH; |
| 12 | it expresses the absence of a fixed improvement below base two across |
| 13 | all fixed clause widths, even when each width has its own algorithm. |
| 14 | |
| 15 | `Randomized` excludes bounded-error randomized algorithms instead. |
| 16 | The polynomial factor in the full formula length is explicit in |
| 17 | `SATTime.Solvable`. These are propositions, not axioms. |
| 18 | -/ |
| 19 | |
| 20 | namespace Lax489179.SETH |
| 21 | |
| 22 | def Hypothesis (mode : Algorithms.Mode) : Prop := |
| 23 | ∀ ε : ℝ, 0 < ε → ε < 1 → |
| 24 | ∃ k : ℕ, 3 ≤ k ∧ ¬ SATTime.Solvable mode k (1 - ε) |
| 25 | |
| 26 | def Deterministic : Prop := Hypothesis .deterministic |
| 27 | |
| 28 | def Randomized : Prop := Hypothesis .randomized |
| 29 | |
| 30 | end Lax489179.SETH |
| 31 |
Community review
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.
0 comments