Nonrelativizing Separations

Harry Buhrman, Lance Fortnow, and Thomas Thierauf

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.