## ← 19-07 Exptime And Nexptime Solution

• 1 Follower
• 33 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=bpakPEiPjmQ" data-team="udacity"></div> ``` 1 Language

• English [en]

Showing Revision 1 created 10/03/2012 by Amara Bot.

1. So each complexity class here follows a number of conditions
2. or has a number of conditions that define it,
3. so P is defined as being the class of all problems
4. that can be solved in polynomial time on a deterministic RAM,
5. and NEXPTIME, for example, is defined
6. as the class of all problems that can be
7. solved in exponential time on a non-deterministic RAM.
8. Now when you want to arrange those classes into a sort of hierarchy,
9. then you always have to think about which conditions
10. are more restrictive than others.
11. And I hope it's clear by now that determinism
12. is more restrictive than non-determinisms.
13. So basically, we can say non-determinism
14. is stronger than determinism.
15. Of course, this is very hand weary,
16. so don't show this to a theoretical computer scientist,
17. but for here it is okay to think about it that way.
18. Now what about exponential time and polynomial time,
19. I think that is a very clear one.
20. So exponential time clearly should give you at least as much power as polynomial time,
21. and this basically gives us the hierarchy,
22. because polynomial time is clearly the most restrictive one,
23. and non-deterministic exponential time is clearly the most powerful one.
24. So we can already say here that P goes into the very inner circle
25. whereas NEXPTIME goes out here.
26. Now what about NP and exponential time on a deterministic machine?
27. When we talked about non-determinism,
28. we already found out that polynomial time non-determinism
29. can always be simulated in exponential time determinism,
30. which means that exponential time on a deterministic machine is
31. at least as powerful as non-deterministic time on a polynomial time machine.
32. So NP goes into the second circle here
33. and EXTIME into the third.