Alphabeta MathHow 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.
Boolean circuits: basis, fan-in, size, and depth
Definition
A Boolean circuit on inputs is a finite directed acyclic graph with inputs , constants and , and NOT, AND, and OR gates; AND and OR have fan-in two, while NOT has fan-in one. One node is designated as the output. The circuit's value is the value at that node after evaluating the graph in topological order. Its size is its number of non-input gates, and its depth is the largest number of non-input gates on a directed path ending at the output (a path may begin at an input or a constant).
If two fixed finite bounded-arity bases can simulate every gate (and every constant) of one another by fixed finite circuits, then changing between them costs only constant factors in size and depth. In particular this holds for any two such functionally complete bases with simulable constants. No such claim is made for an arbitrary finite basis that may fail to express one of the Boolean operations.
Used by
- Reversible embedding of a Boolean circuit Algorithm
- AC0, NC1, and NC under a stated uniformity convention Definition
- Assignment tester and rejection ratio Definition
- Boolean formulas and deterministic branching programs Definition
- Circuit families and P/poly Definition
- Circuit satisfiability Definition
- Shared codeword blocks and edge acceptance circuits Definition
- Boolean circuits become quadratic systems with a fixed input prefix Lemma
- Boolean circuits compile exactly into the QC14 gate alphabet Lemma
- Circuit satisfiability becomes linear-quadratic consistency Lemma
- Counting bounded-size Boolean circuits Lemma
- Gate constraints are a weak assignment tester Lemma
- Ph circuit matrix final block encoding Lemma
- A two-piece constant-query PCP of proximity Theorem
- Element-distinctness gate cost in the QRAM model Theorem
- Every polynomial-time language has polynomial-size circuits Theorem
- Gate, workspace, and serial-depth costs of reversible embedding Theorem
- Parallel depth of reversible Boolean embedding Theorem
Dependency tree · 0 levels
Nothing. This result depends on no other item in the library.
Sources
- Arora and Barak, Computational Complexity: A Modern Approach (standard reference, not scraped)
- Lance Fortnow, Counting Complexity (standard reference, not scraped)