zbMATH — the first resource for mathematics

A logic for constant-depth circuits. (English) Zbl 0592.94023
Summary: Consider a family of Boolean circuits \(C_ 1,C_ 2,...,C_ n,...\), constructed by some uniform, effective procedure operating on input n. Such a procedure provides a concise representation of a family of parallel algorithms for computing Boolean values. A formula of first order logic may also be viewed as a concise representation of a family of parallel algorithms for evaluating Boolean functions. The parallelism is implicit in the quantification (a formula \(\forall x\Phi (x)\) is true if and only if each of the formulas \(\Phi\) (a) is true, and all these formulas can be checked simultaneously), and universes of different sizes give rise to Boolean functions with different numbers of inputs (the Boolean values of the formula’s predicates on various combinations of elements of the universe). This note presents an extended first-order logic designed to be exactly equivalent in expressiveness to polynomial- size, constant-depth, unbounded-fan-in circuits constructed by Turing machines of bounded computational complexity.

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68W99 Algorithms in computer science
68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q65 Abstract data types; algebraic specification
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
03B10 Classical first-order logic
Full Text: DOI