English subtitles

← 19-07 Exptime And Nexptime Solution

Get Embed Code
1 Language

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.