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.
circuits complexity connection polynomial size