[Cst-1b] Complexity - the EXP class

[Martin Harper]

Matthew Richards wrote:

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

Ok - that makes sense, thanks...

> 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))

I don't see that this step works. Surely if, for example k=2,n=3, then k^(n^k) =
2^9, but k^(k^n) = 2^8 ?

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

and that's different again to (k^k)^n, which is 4^3, or 2^6... :(

ugh. I never liked logs...
--
Martin "MyRedDice" Harper - mcnh2@cam.ac.uk - ICQ 23187583
Homepage - http://www.h2g2.com/U129960
This email comes with no warranty.