Abstract:
Diagonalization is a powerful technique in recursion theory and in computational complexity \cite{For00}. The limits of this technique are not clear. On the one hand, many people argue that conflicting relativizations mean a complexity question cannot be resolved using only diagonalization. On the other hand, it is not clear that diagonalization arguments necessarily relativize. In \cite{NIR03}, the authors proposed a definition of ``separation by strong diagonalization'' in which to separate class $AAA$ from $BBB <@= AAA$ a proof is required that $AAA$ contains a {\em universal language} for $BBB$. However, in this paper we show that such an argument does not capture every separation that could be considered to be by diagonalization. Therefore, we consider various weakenings of the notion of universal language and corresponding formalizations of separation by diagonalization. %% that would include this type of intuitively diagonalization argument. We introduce four notions of {\em infinitely-often universal language}. For each notion, we give answers or partial answers to the following questions: \begin{enumerate} \item Under what conditions does the existence of a variant of a universal language for $BBB$ in $AAA$ show $BBB != AAA$? More precisely, what closure properties are needed on $AAA$ and $BBB$? \item Can any separation be reformulated as this kind of diagonalization argument? More precisely, are there complexity classes $BBB <@= AAA$ with nice closure properties, so that $AAA$ has no such variant of a universal language for $BBB$? \item Are these variants of universal language different from the other notions we have defined? \end{enumerate} The main examples of a separation by diagonalization are the time and space hierarchy theorems. We explore the following question: is any separation of a $xP$ from $AAA$ where $AAA$ is closed under polynomial-time Turing reducibility essentially a separation by the time hiearchy theorem?