Separating the polynomial-time hierarchy by oracles

Reviewer: Michael Sipser

This paper solves a long standing, open question by establishing the existence of an oracle separating the union of the polynomial time hierarchy from polynomial space. It further states without proof an extension of this result to obtain an oracle separating all of the levels of the polynomial time hierarchy. The core of this result is an exponential lower bound on the size of constant depth Boolean circuits for computing the parity function. The connection between this circuit size lower bound and the oracle existence question had been previously shown by Furst, Saxe, and Sipser [1]. However, their merely superpolynomial lower bound was not strong enough. Yao's improvement on this result incorporates ideas from this and other previous papers, most notably Boppana's exponential lower bound for monotone circuits [2]. The central point is to analyze the way a function is likely to be simplified by randomly pre-setting a large random subset of its variables. Yao's analysis is deep and intricate. The presentation is well written and thorough, though the complexity of the argument is daunting. Very recently, Hastad (at MIT) has further tightened and greatly simplified Yao's proof [3].