ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-09-12

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Changing between two polynomially related tuple encodings preserves polynomial complexity

Example

Encode a tuple of natural numbers first by the self-delimiting tuple code $σ$ , and second by the code $τ$ obtained by repeating each bit of $σ$ twice. The translation $σ \mapsto τ$ is linear-time by bit doubling, and the translation $τ \mapsto σ$ is linear-time by checking adjacent equal pairs and then deleting one bit from each pair. Because $∣ τ (x) ∣ = 2 ∣ σ (x) ∣$ , the two encodings are polynomially related. Hence any polynomial-time or polynomial-space decider written for one of them remains polynomial for the other.

Facts & Assumptions

Given: The encodings $σ$ and $τ$ described above.

[L1]

Polynomially related encodings preserve polynomial-time and polynomial-space classes when the translations in both directions are polynomially computable, by Polynomially related encodings preserve polynomial-time and polynomial-space classes.

Verification

technique · direct

1.1

The bit-doubling and pair-checking procedures are linear-time and linear-space translations between valid $σ$ -codes and valid $τ$ -codes. Also $∣ τ (x) ∣ = 2 ∣ σ (x) ∣$ for every instance $x$ , so the two code lengths bound each other polynomially.

given

2.1

Therefore the hypotheses of [L1] hold, and [L1] transfers polynomial-time and polynomial-space decidability between the two tuple encodings.

L1step 1.1∎

Depends on

Polynomially related encodings preserve polynomial-time and polynomial-space classes

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

4 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Julian Panetta, ECS 120 Theory of Computation: Asymptotic analysis (cont'd) and time complexity (standard reference, not scraped)