ExampleConstruction: Literature-sourcedVerification: AI-generatedPipeline-generatedprecheck passaudited 2026-09-06

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.

A small computation tableau compiled to Circuit Value

Example

On inputs promised to have length two, consider a fixed machine that reads the two bits and accepts exactly $01$ . A circuit for this computation uses $g_{1} = N O T (x_{1})$ , $g_{2} = A N D (g_{1}, x_{2})$ , and output $g_{2}$ . For $x = 01$ , the values are $g_{1} = g_{2} = 1$ .

Facts & Assumptions

Given: the fixed machine on two-bit inputs and input $x = 01$ .

[L1]

Every fixed polynomial-time machine has a polynomial-size logspace-uniform circuit family deciding its acceptance (Polynomial-time computations have logspace-uniform circuit families).

[L2]

Circuit Value is P-complete under logspace many-one reductions (Circuit Value is P-complete).

Verification

technique · direct evaluation

1.1

On $01$ , $g_{1} = N O T (0) = 1$ and $g_{2} = A N D (1, 1) = 1$ , agreeing with the machine's accepting final state.

givenalgebra

1.2

For every two-bit input, $A N D (N O T (x_{1}), x_{2}) = 1$ exactly when $x_{1} = 0$ and $x_{2} = 1$ . Number the input nodes $1, 2$ and the NOT and AND nodes $3, 4$ , with predecessor lists $(1)$ and $(3, 2)$ and output node $4$ . This fixed circuit can be emitted in constant work space; it is a direct circuit for the promised computation, illustrating the existence assertion in [L1].

givenL1algebraconstruct

2.1

The pair $⟨ C, 01 ⟩$ is therefore a yes-instance of Circuit Value, illustrating the acceptance-preserving reduction in [L2].

L2step 1.2∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

5 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

Arora and Barak, Computational Complexity, Theorem 6.7 and Theorem 6.27 (standard reference, not scraped)