YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Japanese subtitles

← 06-30 SAT is NP-Hard

Get Embed Code
3 Languages

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

  1. NP困難について前にお話ししましたが
  2. ここから還元についてお話しします
    また定義の話に戻りますが
  3. なんらかのNP困難問題から問題Xへ
    還元することができれば問題XはNP困難問題です
  4. 問題Xの答えをNP困難問題を解くために
    使うことができるのです
  5. Xの解き方は少なくともNP困難問題と
    同じぐらい難しい必要があります
  6. それゆえNP困難なのです
  7. 下にいくつかの丸がありますね
  8. NP困難であると示すには
    どうすればよいでしょうか
  9. 他のNP困難問題にまとめます
  10. この問題もNP困難だと示したいので
  11. 同じく隣の問題にまとめます
  12. これを繰り返します
    現実的な方法には思えないかもしれませんね
  13. しかし1971年スティーブン・クックが
    NP困難問題の基本概念を提示しました
  14. それがSATです SATはNP困難として知られています
  15. クックが示した方法は見事なものです
    SATを解けるものは
  16. 多項式時間でシミュレートするために使えます
  17. NPコンピュータは非決定性の選択で このケース以来
  18. NPコンピュータで実行できるものは
    すべてSAT問題に変更できます
  19. それゆえSATはNPのどれよりも難しいのです
  20. クックは私たちにNP困難問題を与えてくれましたが
  21. 今や私たちは他もターゲットとしています
  22. NP困難の問題に取り組む時
    私たちは他の方法で取り組みます
  23. 私たちはSATの取り込みは完了しました
    しかし現在では
  24. NP困難として見なされる多くの問題が存在します
  25. 新しい問題に直面した場合でも
    すでにNP困難として知られているものでしょう
  26. NP困難問題はまとめることができます
  27. そのためSATの方法を試す必要はありません