RELATING POLYNOMIAL-TIME TO CONSTANT DEPTH

Going back to the seminal paper of Furst, Saxe, and Sipser (1984), ana logues between polynomial time classes and constant depth circuit clas ses have been considered in a number of papers. Oracles separating pol ynomial time classes have been obtained by diagonalization making esse ntial use of lower bounds for circuit classes. In this note we show ho w separating oracles can be obtained uniformly from circuit lower boun ds without the need of carrying out a particular diagonalization. Our technical tool is the leaf language approach to the definition of comp lexity classes. (C) 1998-Elsevier Science B.V. All rights reserved.