TR06-051 Authors: Alan Nash, Russell Impagliazzo, Jeff Remmel

Publication: 18th April 2006 22:01

Downloads: 3024

Keywords:

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?