Borel Sets and Circuit Complexity

It is shown that for every k, polynomial-size, depth-k Boolean circuits are more powerful than polynomial-size, depth-(k−1) Boolean circuits. Connections with a problem about Borel sets and other questions are discussed.

Authors

• Michael Sipser

Keywords

No keywords are indexed for this paper.