Infinitely-Often Universal Languages and Diagonalization
Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel · 2006
Diagonalization is a powerful technique in recursion the-ory and in computational complexity [2]. The limits of this technique are not clear. On the one hand, many people ar-gue that conflicting relativizations mean a complexity ques-tion cannot be resolved using only diagonalization. On the other hand, it is not clear that diagonalization arguments necessarily relativize. In [5], the authors proposed a def-inition of “separation by strong diagonalization ” in which to separate class from a proof is required that contains a universal language for . 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 corre-sponding formalizations of separation by diagonalization. We introduce four notions of infinitely-often universal lan-guage. For each notion, we give answers or partial answers to the following questions: 1. Under what conditions does the existence of a variant of a universal language for in show ? More precisely, what closure properties are needed on and ? 2. Can any separation be reformulated as this kind of diagonalization argument? More precisely, are there complexity classes with nice closure proper-ties, so that has no such variant of a universal lan-guage for ? 3. Are these variants of universal language different from the other notions we have defined? The main examples of a separation by diagonalization are the time and space hierarchy theorems. We explore the fol-lowing question: is any separation of a from where is closed under polynomial-time Turing reducibility essen-tially a separation by the time hiearchy theorem? 1.