[Cst-1b] Complexity - the EXP class

Martin Harper mcnh2@cam.ac.uk
Sat, 27 May 2000 18:19:11 +0100


Help, please...

Slide 36 says that PSPACE is contained in EXP.

great! but what's EXP!? And given that the preceding two slides were all about
simulating a non-deterministic machine, where does this fit in, given that
PSPACE is defined on deterministec machines?

Thanks,
Martin.