Proof of `Håstad's clique inapproximability theorem` (1st statement)
groundedproofs/Lax253009Proofs/CliqueHardness.lean · lax-253009
What this proof establishes
- thm✓
Lax253009.Amplification - thm✓
Lax253009.CenteredProjection - thm✓
Lax253009.EncodedReduction - thm✓
Lax253009.FAFComposition - thm✓
Lax253009.FAFLocalTests - thm✓
Lax253009.FAFPatterns - thm✓
Lax253009.FiniteProbability - thm✓
Lax253009.FreshBitSampling - thm✓
Lax253009.GraphEncoding - thm✓
Lax253009.ProjectionEncoding - lem✓
Lax253009.RandomizedContainments - thm✓
Lax253009.RandomizedReduction - thm✓
Lax253009.SamplingParameters - thm✓
Lax253009.TestRepetition - thm✓
Lax253009.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.