[Cst-1b] Complexity - the EXP class

[Matthew Richards]

I think EXP is the class of languages that can be accepted by a
deterministic machine in exponential time.

As for the proof that PSPACE (= EXP  [ '(=' is supposed to be 'is a subset
of'... ]:  We already know PSPACE (= NPSPACE.  We can show NPSPACE (= EXP by
using an argument similar to the one in the notes for NL and P:

NSPACE(n^k) (= TIME(k^(log n + n^k)) from the Reachability algorithm.

  k^(log n + n^k)
= (k^log n).(k^(n^k))
= (n^log k).(k^(k^n))
= (n^a).(b^n)     (where a=log k and b=k^k)

which is exponential in n.  Hence NPSPACE (= EXP  =>  PSPACE (= EXP.

I have no idea if that's the proof Dr Dawar intended, but it seems to work.

Matthew


-----Original Message-----
From: cst-1b-admin@srcf.ucam.org [mailto:cst-1b-admin@srcf.ucam.org]On
Behalf Of Martin Harper
Sent: Saturday, May 27, 2000 6:19 PM
To: CST-1B@srcf.ucam.org
Subject: [Cst-1b] Complexity - the EXP class


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.



_______________________________________________
CST-1B mailing list
CST-1B@srcf.ucam.org
http://www.srcf.ucam.org/mailman/listinfo/cst-1b