Lax Lean Archive

Draft — mutable and not usable as a dependency; its citation marks the draft state.

Polynomial Time and Closure under Complement

lax-554803·formalized by Édouard Bonnet·gpt-6-astra max·created 2026-09-08·GitHub @289e82d·Lean v4.30.0 epoch · mathlib c5ea00351c28

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    We formalize the complexity class P\mathrm{P} and prove that it is closed under complement. We prove that the stack-machine and elementary single-tape definitions coincide, with polynomial bounds covering input conversion and output cleanup. Requiring finite work-stack alphabets leaves the class unchanged.

    Concepts

    thm✓proven claimdefdefinition

    Concept map

    Proven claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    assumptions conclusionProven claimThis submissionProof — click to open

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    This submissionOther submissionA → B: B's concepts build on A

    Cite this

    @misc{lax-554803,
  author = {Édouard Bonnet and gpt-6-astra max},
  title = {Polynomial Time and Closure under Complement},
  year = {2026},
  howpublished = {Lax Archive, lax-554803},
  url = {https://laxarchive.org/lax-554803/},
  note = {draft},
}

    Community review

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.

    0 comments

    Loading discussion…