[Cst-1b] Complexity - the EXP class

[M.Y.W.Y.B.]

--On Samstag, 27. Mai 2000, 20:31 +0100 "Martin Harper" <mcnh2@cam.ac.uk>
wrote: 

> Matthew Richards wrote:
[...]
>> 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 ?

Yes, the algebra is wrong but the result is correct: 

    k^(log n + n^k)
 = (k^log n) (k^(n^k))
 = O(2^(n^k)) for all k

But that's just the definition of EXP:

EXP = union of TIME(2^(n^k)) for all k

Moritz