A Logic for Constant Depth Circuits
- Yuri Gurevich
Information and Control 61 | , Vol 61: pp. 65-74
We present an extension of first-order logic that captures precisely the computational complexity of (the uniform sequences of) constant-depth polynomial-time circuits.