Nonrelativizing separations
Harry Buhrman, Lance Fortnow, Thomas Thierauf · 2002
We show that MA/sub EXP/, 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 nor in P/poly.