Proof of `Håstad's clique inapproximability theorem` (1st statement)
groundedproofs/Lax323828Proofs/CliqueHardness.lean · lax-323828
What this proof establishes
- thm✓
Lax323828.Amplification - thm✓
Lax323828.CenteredProjection - thm✓
Lax323828.EncodedReduction - thm✓
Lax323828.FAFComposition - thm✓
Lax323828.FAFLocalTests - thm✓
Lax323828.FAFPatterns - thm✓
Lax323828.FiniteProbability - thm✓
Lax323828.FreshBitSampling - thm✓
Lax323828.GraphEncoding - thm✓
Lax323828.ProjectionEncoding - lem✓
Lax323828.RandomizedContainments - thm✓
Lax323828.RandomizedReduction - thm✓
Lax323828.SamplingParameters - thm✓
Lax323828.TestRepetition - thm✓
Lax323828.TestSampling
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
The uniform PCP and clique reduction give a polynomial-time fair-tape test for every registered NP language. Rejection tapes certify its complement, so complementary tests combine into a zero-error finite-tape algorithm. The probability-preserving compiler implements it in the registered probabilistic machine model with a worst-case polynomial clock. The reverse inclusion is the proved registered containment ZPP ⊆ NP.