Parity, circuits, and the polynomial-time hierarchy

1984/12/01 by Merrick L. Furst, Merrick Furst, James B. Saxe +1 · 8 citations
Computer Science · #Formal Methods in Verification #Logic, programming, and type systems #VLSI and Analog Circuit Testing

paper · doi:10.1007/bf01744431

crossref issued 1984/12/01 · crossref published 1984/12/01 · crossref published-print 1984/12/01 · openalex publication_date 1984/12/01 · crossref created 2005/06/16 · crossref deposited 2020/04/07 · openalex created_date 2025/10/10 · crossref indexed 2026/06/10 · openalex updated_date 2026/07/28

Cited by

• Cosmological lower bound on the circuit complexity of a small problem in logic
• Languages which capture complexity classes
• Natural Proofs
• Algebrization
• Computational Complexity
• Bounded-width polynomial-size branching programs recognize exactly those languages in NC1
• Quantum Computing since Democritus
• Parity function [wikipedia]
• Regular language [wikipedia]