８．クラスＮＰと多項式時間帰着

内容

1. スライド　1 ８．クラスＮＰと多項式時間帰着
2. スライド　2 クラスＰは決定性ＴＭによって定義された。 この計算機モデルを非決定性に変更する...
3. スライド　3 8-1.非決定性時間限定ＴＭ
4. スライド　4 計算の木と非決定性計算時間
5. スライド　5 時間限定非決定性ＴＭ
6. スライド　6 ８−２．クラスNPの定義
7. スライド　7 クラスＰとクラスＮＰの名前の由来
8. スライド　8 クラスPとクラスNPの関係
9. スライド　9 ８−３．クラスNPの問題
10. スライド　10 非決定性計算例
11. スライド　11 ハミルトン閉路問題のインスタンス１
12. スライド　12 非決定性計算
13. スライド　13 インスタンス２
14. スライド　14 非決定性計算
15. スライド　15 以上より、 次の命題が成り立つ。
16. スライド　16 練習
17. スライド　17 クラスNPの問題２
18. スライド　18 充足可能なインスタンス
19. スライド　19 充足不可能なインスタンス
20. スライド　20 SATの非決定性アルゴリズム
21. スライド　21 １．変数に対して　　　から　　　まで、 　　０か１を非決定的に割り当てる。 ...
22. スライド　22 練習
23. スライド　23 ８−４　TMとNTMの時間の関係
24. スライド　24 Nの分岐の最大値を　　とする。（つまり、計算木において、 どの節点に対しても、...
25. スライド　25 計算木の各頂点に対して， シミュレーションは　　　　　　時間で行える。
26. スライド　26 ８−５.検証可能性
27. スライド　27 多項式時間検証可能性
28. スライド　28 多項式時間検証の例１
29. スライド　29 多項式時間検証の例２
30. スライド　30 クラスNPと検証可能性
31. スライド　31 V
32. スライド　32 V
33. スライド　33 ８−６．多項式時間帰着
34. スライド　34 多項式時間帰着の定義
35. スライド　35 多項式時間帰着のイメージ（要素間）
36. スライド　36 多項式時間帰着のイメージ（クラス）
37. スライド　37 帰着のイメージ
38. スライド　38 帰着とクラスP
39. スライド　39 帰着の例
40. スライド　40 ３SAT
41. スライド　41 変数の個数 自体には 制限が無い ことに注意
42. スライド　42 クリーク問題
43. スライド　43 練習
44. スライド　44 名称：ｋクリーク、 インスタンス： 問：G中に、ｋクリークが存在するか？
45. スライド　45 多項式時間帰着
46. スライド　46 この　　から　　クリーク問題のインスタンスである 　　　　　　を生成する。 ...
47. スライド　47 に対するグラフ　　の構成例を示す。
48. スライド　48 ここで、この帰着が正しく動作することを示す。すなわち、 「　　が充足可能である...
49. スライド　49 十分性：
50. スライド　50 練習