Japanese subtitles

← 06-24 P=NP?

Get Embed Code
3 Languages

Showing Revision 1 created 03/11/2014 by Fran Ontanaya.

  1. コンピュータ・サイエンスの理論において
    最も基本的な質問です
  2. P=NPは成り立つのでしょうか?
  3. 成り立ちます PはNPに
    NPはEXPに属していますから
  4. すべての問題は多項式時間で解けますし
  5. 非決定性多項式時間で解けます
  6. さらに非決定性多項式時間で解くことが可能なら
    指数時間でも解けます
  7. ですがこっちの場合は分かりません
  8. この場合はNPとEXPがイコールです
  9. 非決定性多項式時間で解ける問題は
  10. 指数時間で解ける問題と一致すると
    言えるかもしれません
  11. ここでは内側と外側に分かれています
  12. 内側は多項式時間で解ける問題です
  13. 分かっているのはPとEXPは
    イコールではないということです
  14. 多項式時間と指数時間の間には違いがあります
  15. ある問題は指数時間で解けますが
    明らかにNPではありません
  16. この2つの違いは判明しましたが
  17. NPがxとイコールかどうかは分かりません
    こちらではP=NPです
  18. つまり非決定性多項式時間で解ける問題は
    多項式時間でも解ける問題と同じです
  19. この場合どちらも指数時間とは異なります
  20. 3つの違うカテゴリを表現しました
  21. NP問題は指数時間を必要としませんが
  22. 多項式時間でも解けないかもしれません
    これは分かりません
  23. このケースでP=NPなのかの問題は
    とても重要な問題です
  24. ではP=NPならどうなるのでしょうか?
    解釈は人それぞれ違います
  25. クイズにしますので考えてみてください
  26. 1つの可能性はデータの機密を守る
    暗号プロトコルです
  27. NPに属するプロトコルが
    クラッキングされてしまいます
  28. 2つ目の可能性は
    コンピュータ・サイエンスの理論家です
  29. 問題がなくなったため大勢が職を失いました
  30. 3つめの可能性はP=NPです
  31. コンピュータが人よりも優秀なため
  32. 人力では不可能な問題を解きました
  33. さてどれが正しいと思いますか?