Lax Lean Archive

Compositional polynomial-time computation with black-box subroutines

lax-218471·formalized by Szymon Toruńczyk @szymtor · GPT·registered·created ·GitHub @7fadbfd·Lean v4.33.0 epoch · mathlib db584cd6d46c

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

    Polynomial-time algorithms can be combined using implementations supplied only by existence theorems. We give a structured stack language with calls to a fixed library of input/output contracts and compile it to ordinary finite stack Turing machines. Calls preserve the caller's other stacks and finite control, and reset all private storage. Their exact cost is the callee's running time plus two traversals of each argument and result and four transfer transitions.

    Polynomial bounds on source execution and on call argument and result sizes give polynomial bounds on the compiled machine. The resulting interface supports sequencing, conditionals, loops, and adaptive calls inside verified programs. As a direct public corollary, encoded polynomial-time functions are closed under sequential composition, even when their implementations are supplied only by existence theorems.

    Concepts

    Concept map
    5 concepts
    100%
    Proven claimDefinitionThis submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    assumptions conclusionProven claimStatement 1, 2, … of a claim with several statementsClaim from this submissionProof — open large view for details
    Proof list

    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

    No other submission in the archive builds on this one, and this one builds on none.

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-218471,
  author = {Szymon Toruńczyk and GPT},
  title = {Compositional polynomial-time computation with black-box subroutines},
  year = {2026},
  howpublished = {Lax Archive, lax-218471},
  url = {https://laxarchive.org/lax-218471/},
}

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…