Uniform polynomial-size circuits are in P

The uniformity generator is first promoted from logarithmic space to polynomial time. A generic fanout combinator then constructs the serialized pair code input expected by the verified quadratic circuit evaluator.

Main results

• circuitEvalLanguage_mem_P — serialized circuit evaluation is in P
• UniformPPoly_subset_P — logspace-uniform polynomial-size circuits are in P

theorem Complexity.circuitEvalLanguage_mem_P : CircuitCode.circuitEvalLanguage ∈ P

The language recognized by the verified serialized circuit-family evaluator belongs to P.

theorem Complexity.UniformPPoly_subset_P : UniformPPoly ⊆ P

Logspace-uniform polynomial-size circuit families decide only languages in P. This is the circuits-to-machines direction of Arora–Barak Theorem 6.7.