Draft — mutable and not usable as a dependency; its citation marks the draft state.

Lax489179.SETH

The Strong Exponential Time Hypothesis (SETH)

concepts/Lax489179/SETH.lean · lax-489179

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Concept map

    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Definition

    For every 0<ε<10<\varepsilon<1, there is a width k3k\geq 3 such that kk-CNF satisfiability has no deterministic O(2(1ε)n)O^*(2^{(1-\varepsilon)n}) algorithm. The width may depend on ε\varepsilon. 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.

    RandomizedRandomized excludes bounded-error randomized algorithms instead. The polynomial factor in the full formula length is explicit in SATTime.SolvableSATTime.Solvable. These are propositions, not axioms.

    Lean source view on GitHub

    1import Lax489179.SATTime
    2
    3/-!
    4---
    5title: The Strong Exponential Time Hypothesis (SETH)
    6type: definition
    7---
    8For every 0<ε<10<\varepsilon<1, there is a width k3k\geq 3 such that
    9kk-CNF satisfiability has no deterministic
    10O(2(1ε)n)O^*(2^{(1-\varepsilon)n}) algorithm. The width may depend on
    11ε\varepsilon. This is the exponential-rate formulation of SETH;
    12it expresses the absence of a fixed improvement below base two across
    13all fixed clause widths, even when each width has its own algorithm.
    14
    15`Randomized` excludes bounded-error randomized algorithms instead.
    16The polynomial factor in the full formula length is explicit in
    17`SATTime.Solvable`. These are propositions, not axioms.
    18-/
    19
    20namespace Lax489179.SETH
    21
    22def Hypothesis (mode : Algorithms.Mode) : Prop :=
    23 ∀ ε : ℝ, 0 < ε → ε < 1
    24 ∃ k : ℕ, 3 ≤ k ∧ ¬ SATTime.Solvable mode k (1 - ε)
    25
    26def Deterministic : Prop := Hypothesis .deterministic
    27
    28def Randomized : Prop := Hypothesis .randomized
    29
    30end Lax489179.SETH
    31

    From Mathlib

    none

    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

    Loading discussion…