Lax Lean Archive

Version history

Submission versions

  1. lax-783278current version

    Arc Kayles is PSPACE-complete

    Created Lean v4.33.0mathlib db584cd6d46c92f209a44c0f1c829460d327499d
    GitHub sourceOpen version
  2. lax-689614viewing

    Arc Kayles is PSPACE-complete

    Created Lean v4.33.0mathlib db584cd6d46c92f209a44c0f1c829460d327499d
    GitHub sourceShown on this page

Proof of `Correctness and complexity of the reduction` (1st statement)

groundedproofs/Lax689614Proofs/FalseSimulation.lean · lax-689614

What this proof establishes

thm✓Lax689614.Reduction (1st statement)

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

False responds to each regular move by following a winning CNF strategy. An exhausted clause supplies a zero-valued exceptional reply. Nonregular moves are losing deviations, including the exceptional move at odd parity.