TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedverified 2026-09-26 (gpt-6-sol)

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.

Circuit Value is P-complete

Statement

Let CIRCUIT-VALUE contain pairs $⟨ C, x ⟩$ where $C$ is a valid topologically ordered single-output Boolean circuit and its output on $x$ is one. Then CIRCUIT-VALUE is P-complete under logspace reductions.

Facts & Assumptions

Given: a circuit-value instance, or an arbitrary language $A \in P$ .

[L1]

A P-completeness proof needs membership in P and a logspace reduction from every language in P (P-completeness under logspace reductions).

[L2]

Every fixed deterministic P machine has a polynomial-size logspace-uniform computation-circuit family (Polynomial-time computations have logspace-uniform circuit families).

Proof

technique · evaluation and uniform compilation

1.1givenconstruct

On an arbitrary encoded pair, first check in polynomial time that the circuit syntax, input arity, single output, and predecessor indices form a valid topological ordering; reject malformed pairs. For a valid circuit, evaluate gates in that order, retaining their values in an array and applying the fixed basis operation at each gate. This takes time polynomial in the encoding length, so CIRCUIT-VALUE is in P.

1.2L2construct

For $A \in P$ , choose its fixed P decider $M$ and the family $(C_{n})$ supplied by [L2]. On $x$ of length $n$ , output $⟨ C_{n}, x ⟩$ by streaming the uniform circuit description and then copying $x$ .

2.1L2step 1.2algebra

The transducer keeps only an $O (\log n)$ -bit circuit-query index and its output position; [L2] answers each requested gate query in logspace. Thus $x \mapsto ⟨ C_{∣ x ∣}, x ⟩$ is a logspace reduction, and it preserves acceptance.

3.1L1step 1.1step 2.1∎

Step 1.1 gives membership and step 2.1 gives hardness for arbitrary $A \in P$ ; [L1] therefore gives P-completeness.

Depends on

Used by

A small computation tableau compiled to Circuit Value Example

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.27 (standard reference, not scraped)