English subtitles

← 09-01 Seed Problem

Get Embed Code
1 Language

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

  1. Now the hardest part is done.
  2. We have a problem we know to be NP complete,
  3. and that problem SAT.
  4. So from now on, showing that other problems are NP complete
  5. will get a lot easier,
  6. because we don't have to go through this
  7. laborous process n coding machines anymore
  8. It will just suffice to show that SAT
  9. can be reduced the the problem we're looking at.
  10. So we can use SAT to show other problems
  11. to be NP complete now,
  12. and once we have shown these problems to be NP complete,
  13. we can use them as well to show
  14. again, other problems to be NP complete,
  15. so we are basically building this whole tree of NP complete problems
  16. using SAT as a c problem
  17. and it will just suffice to show these
  18. reductions here; we do not have to
  19. do the same tedious steps of Boolean formula n coding anymore,
  20. because we already know SAT to be NP complete now.
  21. So let's take 1 step back now
  22. with our next quiz.
  23. What happens if you show one NP complete problem
  24. to be solvable in polynomial time?
  25. And by solvable in polynomial time, of course,
  26. I mean on a deterministic RAM.
  27. Would that mean that some problems in an NP
  28. can be solved in polynomial time?
  29. Again, we're talking about a deterministic RAM here.
  30. Would it mean that all NP complete problems
  31. are solvable in polynomial time?
  32. Or would it mean that all problems in NP
  33. are solvable in polynomial time?
  34. And again, more than 1 of these answers here can be correct,
  35. so please check every statement that is correct.