Skip to content

feat(api): register plain resource notions with fun_prop #556

Closed

Description

@SamuelSchlesinger

Follow-up to #551 / #555 (M1b of #456). The design commitments say computability predicates are @[fun_prop]-registered. #554 does this for ComputableInPolyTime. The plain resource notions added in #555 are not registered yet, so a plain goal has to go through .tidy/.of_tidy by hand.

Scope

  • In Complexity/Computability/Machines/Turing/MultiTape/Complexity/PolySpace/Plain.lean, mirroring refactor(api): add plain polynomial-time computability with tidy bridges #554's PolyTime/Plain.lean:
    • attribute [fun_prop] ComputableInPolySpace.
    • @[fun_prop] on ComputableTidilyInPolySpace.computableInPolySpace as the tidy-to-plain transition rule.
    • Plain closure rules proved through .tidy, matching the tidy set at PolySpace.lean:143 (of_polyTime, id', prod, ite, comp').
    • of_polyTime takes refactor(api): add plain polynomial-time computability with tidy bridges #554's ComputableInPolyTime.
  • Optional, same pattern: ComputableInFPTTime in Parameterized.lean, with ite and composition along a parameter bound. ComputableInO/ComputableInSpace carry explicit bounds, so they are less natural fun_prop targets; register them only if a consumer needs it.

Consumers. These are the M3 restatements of polynomial-space results that build deciders compositionally today with tidy fun_prop/combinators:

  • setOf_exists_mem_PSPACE, mem_PSPACE_iff_computableTidilyInPolySpace and PolyTimeReducible.mem_PSPACE (Classes/Inclusions.lean)
  • Classes/Counting/Space.lean, Classes/SharpP/Space.lean
  • Classes/IP/PSPACE.lean, Classes/IP/Simulation.lean
  • Classes/Space/TM2.lean

Done when: a plain ComputableInPolySpace goal built from plain and tidy parts closes by fun_prop, with a test client, and the six gates pass.

Depends on #555 and #554.


Opened by worker-claude-551-c4b0c164 (Claude Code, Opus 5.5), delegated by coordinator-claude-c4b0c164-20261023, at the request of the #555 review.

Activity

  1. SamuelSchlesinger commented on Oct 23, 2026

    @SamuelSchlesinger
    CollaboratorAuthor

    Claimed by implementation worker codex-worker-556-01a16ab8, delegated by coordinator-codex-01a16ab8. Scope: plain polynomial-space fun_prop registration, tidy-to-plain transition and the five scoped closure rules, with mixed plain/tidy and representative consumer clients. Optional FPT automation is left out unless an actual consumer requires it. Branch feat/plain-polyspace-automation-556, isolated worktree /home/samuel/Code/complexitylib-wt/codex-556; mutable build caches will be copied independently. State: active.

  2. SamuelSchlesinger commented on Oct 23, 2026

    @SamuelSchlesinger
    CollaboratorAuthor

    Worker codex-worker-556-01a16ab8: awaiting independent correctness/API review in #571 at ea6874fd77fadf06d602307bfcf1960a8da4ca13. All six gates, hygiene and catalogue checks pass; validation and abstract assessment are recorded in the PR. Optional FPT automation is omitted because this scope has no consumer requiring it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Labels

No labels
No labels

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions