
Title:
1907 Exptime And Nexptime Solution

Description:

So each complexity class here follows a number of conditions

or has a number of conditions that define it,

so P is defined as being the class of all problems

that can be solved in polynomial time on a deterministic RAM,

and NEXPTIME, for example, is defined

as the class of all problems that can be

solved in exponential time on a nondeterministic RAM.

Now when you want to arrange those classes into a sort of hierarchy,

then you always have to think about which conditions

are more restrictive than others.

And I hope it's clear by now that determinism

is more restrictive than nondeterminisms.

So basically, we can say nondeterminism

is stronger than determinism.

Of course, this is very hand weary,

so don't show this to a theoretical computer scientist,

but for here it is okay to think about it that way.

Now what about exponential time and polynomial time,

I think that is a very clear one.

So exponential time clearly should give you at least as much power as polynomial time,

and this basically gives us the hierarchy,

because polynomial time is clearly the most restrictive one,

and nondeterministic exponential time is clearly the most powerful one.

So we can already say here that P goes into the very inner circle

whereas NEXPTIME goes out here.

Now what about NP and exponential time on a deterministic machine?

When we talked about nondeterminism,

we already found out that polynomial time nondeterminism

can always be simulated in exponential time determinism,

which means that exponential time on a deterministic machine is

at least as powerful as nondeterministic time on a polynomial time machine.

So NP goes into the second circle here

and EXTIME into the third.