Proof of `QPTAS for maximum-weight independent set`
groundedproofs/Lax263307Proofs/MainTheorem.lean · lax-263307
What this proof establishes
- thm✓
Lax109476.CertificateSoundness - thm✓
Lax109476.PolynomialTimeSolver - thm✓
Lax263307.AlgorithmParameters - thm✓
Lax263307.BlowUpBagBounds - thm✓
Lax263307.BlowUpClasses - thm✓
Lax263307.BufferedEllipsoid - thm✓
Lax263307.ComputedRounding - thm✓
Lax263307.ComputedSeparators - thm✓
Lax263307.CoordinateCatalog - thm✓
Lax263307.DistanceProjection - thm✓
Lax263307.ExhaustiveTargets - thm✓
Lax263307.HeavyRationalConditioning - thm✓
Lax263307.MomentLP - thm✓
Lax263307.PositiveWeights - thm✓
Lax263307.RationalConditioning - thm✓
Lax263307.RationalCutBuffer - thm✓
Lax263307.RationalProjection - thm✓
Lax263307.RecursionDepth - thm✓
Lax263307.RelaxationFeasibility - thm✓
Lax263307.RoundedOracleSearch - thm✓
Lax263307.TargetSearch - thm✓
Lax263307.WeightedProjection
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
Select the fixed registered backends and rounded-update program once. The complete weighted source specification is compiled through the registered RAM refinement framework. Its checked root-resource estimates and logarithmic recursion bound give the asserted quasipolynomial time and word width.