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

Lax47.Hastad

Håstad's inapproximability of Max Independent Set

concepts/Lax47/Hastad.lean · lax-47

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

    Håstad's general-graph inapproximability result supplies the hardness premise used by the reduction. We use its equivalent rational promise-gap form. For every integer q>2q>2, a bounded-error polynomial-step algorithm distinguishing nn-vertex graphs HH with α(H)n1/q\alpha(H)\leq n^{1/q} from those with n11/qα(H)n^{1-1/q}\leq\alpha(H) would imply NPBPPNP\subseteq BPP.

    This concept only defines that premise. It does not assert Håstad's result as an archive axiom; the main theorem of this submission is the implication from this premise to the triangle-free inapproximability conclusion.

    Lean source view on GitHub

    1import Lax47.Gap
    2
    3/-!
    4---
    5title: Håstad's inapproximability of Max Independent Set
    6type: definition
    7---
    8Håstad's general-graph inapproximability result supplies the hardness premise
    9used by the reduction. We use its equivalent rational promise-gap form. For
    10every integer q>2q>2, a bounded-error polynomial-step algorithm distinguishing
    11nn-vertex graphs HH with α(H)n1/q\alpha(H)\leq n^{1/q} from those with
    12n11/qα(H)n^{1-1/q}\leq\alpha(H) would imply NPBPPNP\subseteq BPP.
    13
    14This concept only defines that premise. It does not assert Håstad's result as
    15an archive axiom; the main theorem of this submission is the implication from
    16this premise to the triangle-free inapproximability conclusion.
    17-/
    18
    19set_option autoImplicit false
    20
    21namespace Lax47.Hastad
    22
    23open Lax47.Machine Lax47.Gap
    24
    25/-- Håstad's general-graph promise-gap inapproximability premise. -/
    26def Inapproximability : Prop :=
    27 ∀ q : ℕ, 3 ≤ q → MISGapSolver q → NPSubsetBPP
    28
    29end Lax47.Hastad
    30

    Builds on

    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…