A Topological View of Some Problems in Complexity Theory
We present a new, combinatorial proof of the classical theorem that the analytic sets are not closed under complement. Possible connections with questions in complexity theory are discussed.