Parity, Circuits, and the Polynomial-Time Hierarchy.

Merrick L. Furst James B. Saxe Michael Sipser

Published in: Math. Syst. Theory (1984)

Keyphrases

error correction
special case
computational complexity
high speed
truth table
worst case
lower level
higher level
hierarchical structure
approximation algorithms
polynomial time complexity
np hard
machine learning
finite automata
np hardness
digital circuits
dnf formulas
class hierarchy