
\section{Overview}

A primary focus of structural complexity theory is
showing that a class contains a language which
in fact can not be computed with less resources. In 
this way complexity classes are shown to be distinct or separate. 
Intuitively, increasing the amount of resources should 
allow us to recognize more languages.   
In fact various separation results are known between
nondeterministic time classes 
\cite{Cook73,SeiferasFischerMeyer,BookGreibach}
and between deterministic time classes
\cite{HartmanisStearns}.
Although of great practical interest, 
separations between nondeterministic and deterministic 
classes of the same time complexity have not been proved.
This proposal outlines an approach which we believe will be useful in 
separating exponential time-bounded classes from lower complexity classes.

Problems for which there is no known solution in polynomial time; i.e.,
no known efficient solution, 
are considered to be intractable
\footnote{In different parts of the literature problems in
both $P$, deterministic polynomial time, and $BPP$,
the class of languages recognized by polynomial
time probabilistic Turing machines whose error
is bounded above by some positive constant $\epsilon < 1/2$ ,
have been considered tractable.}.
These problems
have been broadly categorized as exponential time problems
even though this includes 
problems in subexponential classes such as $TIME(n^{\log n})$ 
\cite{GareyJohnson}.
Our proposed research will
focus on the exponential time classes $EXP$, $NEXP$ 
and classes in the related exponential time hierarchy, $EXPH$.
It should be noted that there are several different ways
to define exponentially time-bounded classes.
In this proposal $EXP$ will be used to refer to the
set of languages in $DTIME(2^{p(n)})$, where $p$ is a polynomial, and
$NEXP$ will be used to refer to the set of languages in $NTIME(2^{p(n)})$.
Likewise, $E \cs (NE)$ will be used to refer to
the set of languages in $DTIME(2^{cn}) \cs (NTIME(2^{cn}))$ respectively,
where $c$ is any constant. 
The following containments are known:
\[ P \subseteq NP \subseteq PH \subseteq PSPACE \subseteq EXP \subseteq NEXP\]
where $PH$ is the polynomial time hierarchy and $PSPACE$ refers to 
the set of languages in $SPACE(p(n))$. 
By time hierarchy theorems, 
the following proper containments are known
\cite{HartmanisStearns,HartmanisLewisStearns,Cook73,Mocas2}:
\[P \subsetneq E \subsetneq EXP  
\mbox{ and }  NP \subsetneq NE \subsetneq NEXP \mbox{ and } 
P^{NP[n^c]} \subsetneq NEXP. \]
The last result improves the separation $NP \subsetneq NEXP$
since $NP \subseteq P^{NP[n^c]} \subsetneq NEXP$
\footnote{ 
$P^{NP [f(n)]}$ is the set of all languages 
computed deterministically by a polynomial time-bounded
oracle Turing machine which, on input $x$, makes at most
$O(f(|x|))$ queries to an $NP$ set.
For example,
optimization versions of many problems 
in $NP$ are complete for $P^{NP[\log]}$ or $P^{NP[poly]}$
\cite{Krentel}
.}. 
Surprisingly, with the exception of the last statement, proofs of    
the above separations results date from  early work in complexity theory
and have not been improved.
Many interesting questions, 
one of which is the  proper containment of $NP$ in $EXP$,
are still open and appear to be difficult to prove.  

% Mocas has shown that 
% $P^{NP[n^c]} \subsetneq NEXP$ for any integer $c$
% \cite{Mocas}.  Improving these result will require nonrelativizing 
% proof techniques and, 
% for this reason, showing further separation of $EXP$ and $NEXP$
% from polynomial time classes has been considered difficult.
% A related result by Kannan separates the second level of the
% exponential time hierarchy, $NEXP^{NP}$, from the 
% polynomial time probabilistic class $BPP$.


Relativized results are used as a tool to indicates the difficulty of
resolving a proposition in the unrelativized case.
Intuitively, if a relationship between two sets is known,
for example, $A \neq B$, then allowing machines which
compute the membership of each set to have access
to an additional resource should not change the inequality relationship.
So if machines for recognizing elements in $A$ and $B$ 
have access to a resource that decides membership for a set $C$, then
$A^C \neq B^C$ should be true. $C$ in this contexts is roughly used as an
oracle set.  
A complexity theoretical statment {\em relativizes} if
the truth of the statement remains unchanged in the presents of any 
oracle set. 
In general, the proof techniques which have traditionally been used
in complexity theory relativize.
For example, the statement $NP \neq NEXP$ relativizes 
since $NP^A \neq NEXP^A$ for any set $A$ used as an oracle, but the statement 
$P \neq NP$ does not relativize since there is an oracle such that
relative to that set $P \neq NP$ and a different oracle such that 
relative to it $P = NP$
\cite{BakerGillSolovay}.
Many of the central questions in complexity theory
have results which are optimal
with respect to relativization.
For example, it is known that $P^{NP[n^c]} \subsetneq NEXP$, 
for any fixed constant $c$,
\cite{Mocas,Mocas2} and that this result can not be improved using 
proof techniques which relativize
\cite{BuhrmanTorenvliet}.  
In other words, Buhrman and Torenvliet show that there is an
oracle set relative to which $P^{NP[poly]} = NEXP$.  An oracle 
relative to which these classes are not equal is easily constructed
using a $NEXP$-complete set as an oracle. 
To make head-way in answering many of the open
questions  in structural complexity,
proof techniques which do not relativize are needed. 
Please see section 3.1.2 for a brief review of oracle results that 
relate specifically to exponential time classes and the proposed research.

In the last few years, 
results using non-relativizing proof techniques have appeared
\cite{Shamir,BabaiFortnowLund,AroraLundMotwaniSudanSzegedy}. 
The introduction of non-relativizing proof techniques holds great promise
that some of the current fundamental questions, which are known not
to have relativizing proofs, can be resolved.
Unfortunately this has not happened to date.  
Never the less, these proof techniques 
form an important first step in this direction.
Our intention is to investigate exponential time classes defined 
via models which are shown, using  nonrelativizing proof techniques,
to encompass standard complexity classes.
Specifically we propose to characterize  classes in the
exponential time hierarchy
in terms of these models with the intention of
showing separations using these characterizations.
Note that $NEXP$ has already been characterized via two 
probabilistic models, since 
$NEXP =  MIP$ 
\cite{BabaiFortnowLund}
and  $NEXP = PCP(poly, poly)$  
\cite{AroraLundMotwaniSudanSzegedy}. 
Multiple interactive proofs, 
$MIP$, characterizes $NEXP$ via two prover interactive proof systems and 
the probabilisticly checkable proof model,
$PCP$, uses random access to a fixed proof (with no interaction).
$EXPSPACE$ has also been characterized as a probabilistic game
\cite{BuhrmanFortnowTorenvliet}.
We propose using the characterization for EXPSPACE in terms
of a probabilistic game (as given in 
\cite{BuhrmanFortnowTorenvliet} )
to characterize classes in the exponential time hierarchy
in the same manner in which probabilisticly checkable debate systems,
PCD's, were used to characterize the levels of the polynomial hierarchy 
\cite{CondonFeigenbaumLundShor,KiwiLundRussellSpielmanSundaram}.
It is our hope that an examination of non-relativizing
proof techniques in a different environment; 
i. e., high time classes, will give some intuition as to their
strengths and weaknesses.

The $PCD$ model is closely related to the alternating Turing machine
model of 
\cite{ChandraStockmeyer}. 
The proof of the collapse of the polynomial time hierarch, 
under the assumption that $P=NP$, is closely tied to Stockmeyer's
definition of the polynomial time hierarchy via alternating
universal and existential quantifiers
\cite{Stockmeyer}.  
This particular characterization
can not be directly used to show that the exponential time hierarchy 
collapses under the similar assumption that $EXP=NEXP$.
The exponential time hierarchy is most naturally defined via 
alternating Turing machines.  Although there is a direct relationship
between the alternating Turing machine model and the alternating
quantifier model they are not interchangeable in the context of some proofs
and specifically with regard to exponential time classes.
It is for this reason there is interest in  finding yet another
way in which to define classes in $EXPH$.  It is hoped that 
defining classes in $EXPH$ via proof models will lead to new results
about these classes.

There is strong justification for examining complexity classes that are not
computationally feasible since
resolving many of the open questions for high time/space classes
implies similar results for corresponding lower classes.
For example, it is known that if exponential time 
deterministic and nondeterministic
classes are not equal then there are corresponding lower classes
that are also not equal (see section 3.1.1 for details).  
So showing that $EXP \neq NEXP$ implies $P \neq NP$. 
This particular exponential time problem is probably not structurally different
form it's polynomial counterpart but there are important open 
questions concerning exponential time classes where the classes involved 
appear to be structurally different from their polynomial time
counterparts and yet answering such questions still implies 
corresponding results for lower time classes.


The structure of exponential time classes does not always mirror
that of related polynomial time classes. 
Specifically, some of the techniques which are used to 
demonstrate results in the polynomial time hierarchy do not
generalize to exponential time hierarchies.   For
one, it has not been shown that general downward separating
results which apply to the polynomial time hierarchy 
can be duplicated in  natural exponential time hierarchies.
The exponential 
time hierarchy is not know to collapse under the assumption that
$EXP = NEXP$ where as the polynomial time hierarchy collapses 
under the assumption that $P = NP$.  If, in fact, the exponential 
hierarchy were known to collapse under this assumption then
it would easily follow that $PH \subsetneq NEXP$ which remains
an open question. 
For this reason, we specifically propose to characterize classes in the
exponential time hierarchy, $EXPH$, 
using probabilistic models in the hopes that
this characterization can be used to show general separations.
We do not anticipate that a probabilistic model for classes in
$EXPH$ will exactly mirror the probabilistic model
which has been used to define classes in $PH$
\cite{KiwiLundRussellSpielmanSundaram}.


% It is well known that results for
% higher time classes usually imply similar results in lower 
% time classes.
% Further, it is known  that the the finer structure of exponential time 
% classes is not exactly the same that of classes below exponential time.
In the process of studying exponential time classes and 
their relationship to polynomial time classes several interesting questions 
have come to the forefront.
Specifically, the following questions have directly motivated
this proposal. 
\begin{tabbing}
aa \= aaa \= aaa \kill
\> Is $P^{NP}$ properly contained in $NEXP$? \\
\> Is $BPP$ properly contained in $NEXP$? \\
\> Does $\co NEXP \subseteq NEXP$ imply that 
		the exponential time hierarchy collapses? 
\end{tabbing}
None of these questions has been answered.
A positive answer to the last question would separate $NEXP$ from
the polynomial time hierarchy, $PH$.

To summerize, 
our goal is two fold, we wish to 
study the structure of high time/space classes described via 
nonrelativizing models and also to 
show separations between exponential time classes
and classes in the polynomial hierarchy using these characterizations. 
First we intend to see if the characterization for $EXPSPACE$ in terms
of a probabilistic game (as given in 
\cite{BuhrmanFortnowTorenvliet} )
can be used to characterize classes in $EXPH$ in the same manner in which
PCD's were used to characterize classes in $PH$
\cite{CondonFeigenbaumLundShor,KiwiLundRussellSpielmanSundaram}.
Such a characterization will be studied to see a collapse of the exponential
time hierarchy can be proved 
using this characterization and 
given an assumption, such as $NEXP=EXP$.
We are interested in this since the collapse of $EXPH$ to some level
can be used to separate classes in $EXPH$ from classes in the 
polynomial time hierarchy.
Finally, we intend to study classes such as $PCP(n^c, poly)$ and
$PCP_{EXP}(2^{n^c}, exp)$ to see if any of the standard complexity
classes above $P^{NP[n^c]}$ and $EXP^{NP[poly]}$, respectively, can be shown to 
be contained in these classes.  If so this may give a new proper
subset of $NEXP$. 

Current work, done under NSF grant number CCR-9410713,  
gives an indication of the potential for this line of research.
We show that, by considering the structure of the probabilistically
checkable proof model,
$PCP$,
diagonalization can be used to separate the classes 
$PCP(n^c, poly)$ and $NEXP$.  This is of interest 
$PCP(poly, poly) = NEXP$ and, further,  
showing any class to be in $PCP(n^c, poly)$ would then show the proper 
inclusion of that class in $NEXP$. 
Proof of the following, unpublished theorem in included.

\begin{theorem}
For any fixed constant $c$, $PCP(n^c,poly)$ is a proper subset of $NEXP$.
\end{theorem}

Since it has been shown that $NEXP = PCP(poly, poly)$  we get 
as a corollary that
for any fixed constant $c$, $PCP(n^c, poly) \subsetneq PCP(poly, poly)$.
Clearly this implies $NP \subsetneq NEXP$ since $NP = PCP(log, 1)$.
The obvious questions is:
Is there some class $A$ which contains $P^{NP[n^{d}]}$, for a fixed $d$, 
and is in $NEXP$ 
such that $A \in PCP(n^c, poly)$?  This would give a new separation
from $NEXP$. One possible class to consider is $BPP$ since it 
is not know if $BPP$ is a proper subset of $NEXP$ or not. 

 
The section called Preliminaries gives useful definitions.
Section 3 contains a more detailed discussion of the 
points just mentioned in the overview.  This includes
a brief history of work previously done on this topic and
an explanation of how the proposed work relates to previous work.
The last part of section 3 includes several theorems and proofs that 
demonstrate directly the type of work proposed.  These theorems
are current work and as yet not submitted for publication.



  
