Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-051 | 8th April 2006 00:00

Infinitely-Often Universal Languages and Diagonalization


Authors: Alan Nash, Russell Impagliazzo, Jeff Remmel
Publication: 18th April 2006 22:01
Downloads: 1078


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:
\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?
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?

ISSN 1433-8092 | Imprint