definition
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
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 , a bounded-error polynomial-step algorithm distinguishing -vertex graphs with from those with would imply .
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
| 1 | import Lax47.Gap |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Håstad's inapproximability of Max Independent Set |
| 6 | type: definition |
| 7 | --- |
| 8 | Håstad's general-graph inapproximability result supplies the hardness premise |
| 9 | used by the reduction. We use its equivalent rational promise-gap form. For |
| 10 | every integer , a bounded-error polynomial-step algorithm distinguishing |
| 11 | -vertex graphs with from those with |
| 12 | would imply . |
| 13 | |
| 14 | This concept only defines that premise. It does not assert Håstad's result as |
| 15 | an archive axiom; the main theorem of this submission is the implication from |
| 16 | this premise to the triangle-free inapproximability conclusion. |
| 17 | -/ |
| 18 | |
| 19 | set_option autoImplicit false |
| 20 | |
| 21 | namespace Lax47.Hastad |
| 22 | |
| 23 | open Lax47.Machine Lax47.Gap |
| 24 | |
| 25 | /-- Håstad's general-graph promise-gap inapproximability premise. -/ |
| 26 | def Inapproximability : Prop := |
| 27 | ∀ q : ℕ, 3 ≤ q → MISGapSolver q → NPSubsetBPP |
| 28 | |
| 29 | end Lax47.Hastad |
| 30 |
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