Fixed points are p and pspace
NOT A NOVELTY CLAIM. This is a machine-checked formalisation, decided by the Lean 4 kernel and depending on no axiom. It is dated and citable. Prior art, where it exists, is cited below. No discovery is claimed.
The classes σ fixes are exactly those closed under complement. P and PSPACE are; the status of NP is the open question.
Proposition
(classes.filter (fun c => σ c == c)) = [P, PSPACE]Proof
By decide in p-vs-np.lean. The kernel reduces the proposition and reports no axiom dependency.
Sources and identifiers
- Lean source · src/pair/formal/proofs/p-vs-np.lean
- Typeset paper · src/research/lean-theorems.tex
- Repository deposit · doi:10.5281/zenodo.21787144
- Author · ORCID 0009-0000-7312-9778
- Deposit record ·
p-vs-np--fixed_points_are_p_and_pspace