A Note on ${\bf NP}\cap{\bf coNP}{\rm /poly}$

Vinodchandran N. Variyam

August 2000

Abstract:

In this note we show that ${\bf AM}_{\small\bf exp} \not\subseteq{\bf NP}\cap{\bf coNP}{\rm /poly}$, where ${\bf AM}_{\small\bf exp}$ denotes the exponential version of the class ${\bf AM}$. The main part of the proof is a collapse of ${\bf EXP}$ to ${\bf AM}$ under the assumption that ${\bf EXP}\subseteq{\bf NP}\cap{\bf coNP}{\rm /poly}$

Available as PostScript, PDF, DVI.

Last modified: 2003-06-08 by webmaster.