Abstract
We show several unconditional lower bounds for exponential time classes
against polynomial time classes with advice, including:
\begin{enumerate}
\item For any constant c, \NEXP\P\NP[nc]nc
\item For any constant c, \MAEXP\MAnc
\item \BPEXP\BPPno(1)
\end{enumerate}
It was previously unknown even whether \NEXP\NPn001 .
For the probabilistic classes, no lower bounds for uniform exponential time
against advice were known before.
We also consider the question of whether these lower bounds can be made to work on almost all input lengths rather than on infinitely many. We give an oracle relative to which \NEXP\io\NP, which provides evidence that this
is not possible with current techniques.
against polynomial time classes with advice, including:
\begin{enumerate}
\item For any constant c, \NEXP\P\NP[nc]nc
\item For any constant c, \MAEXP\MAnc
\item \BPEXP\BPPno(1)
\end{enumerate}
It was previously unknown even whether \NEXP\NPn001 .
For the probabilistic classes, no lower bounds for uniform exponential time
against advice were known before.
We also consider the question of whether these lower bounds can be made to work on almost all input lengths rather than on infinitely many. We give an oracle relative to which \NEXP\io\NP, which provides evidence that this
is not possible with current techniques.
| Original language | English |
|---|---|
| Title of host publication | Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I |
| Pages | 195-209 |
| Number of pages | 15 |
| DOIs | |
| Publication status | Published - 2009 |