Harry Buhrman, Lance Fortnow, and Thomas Thierauf
Abstract:
We show that MAEXP, the exponential time version of the Merlin-Arthur class,
does not have polynomial size circuits. This significantly improves the
previous known result due to Kannan since we furthermore show that our result
does not relativize.
This is the first separation result in complexity theory
that does not relativize. As a corollary to our separation result
we also obtain that PEXP, the exponential time version of PP,
is not in P/poly.