A Note on NP intersection coNP/poly

Vinodchandran N. Variyam

Abstract


In this note we show that AMexp is not in NP intersection coNP/poly, where
AMexp denotes the exponential version of the class AM. The main
part of the proof is a collapse of EXP to AM under the assumption
that EXP is in NP intersection coNP/poly

Full Text:

PDF


DOI: http://dx.doi.org/10.7146/brics.v7i19.20146
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.
OK


ISSN: 0909-0878 

Hosted by the Royal Danish Library and Aarhus University Library