10．PとNP完全問題との境界

内容

1. スライド　1 10．PとNP完全問題との境界
2. スライド　2 １０−１．２SAT
3. スライド　3 例
4. スライド　4 したがって、　　　　　　である。
5. スライド　5 この例の方針にしたがって、 多項式時間アルゴリズムが得られる。
6. スライド　6 証明
7. スライド　7 ここｋで、アルゴリズム２SATが最悪でも 多項式時間で動作することを示す。
8. スライド　8 以上より、次のような状態であることがわかる。
9. スライド　9 練習
10. スライド　10 １０−２．２次元マッチング
11. スライド　11 先ほどの問題は、グラフの問題として定式化できる。
12. スライド　12 肯定のインスタンス
13. スライド　13 否定のインスタンス
14. スライド　14 とする。
15. スライド　15 a
16. スライド　16 a
17. スライド　17 a
18. スライド　18 非マッチの点から初めて非マッチの点で終わる交互道は、 スイッチすることによって...
19. スライド　19 つまり、このような交互道の選択ステップが失敗するならば、 完全マッチングが存在...
20. スライド　20 練習
21. スライド　21 １０−３.３次元マッチング
22. スライド　22 とする。
23. スライド　23 ここでは、３SATを多項式時間で３DMに帰着できることを 示す。
24. スライド　24 まず、A,B,Cを次のように定める。
25. スライド　25 各節は下図のように構成する。
26. スライド　26 ３SATが充足可能であるときにかつ、そのときに限り、 この構成が３DMを持つこ...
27. スライド　27 節に対応するマッチングにより、Aの要素をいずれかの変数で 網羅しなければならな...
28. スライド　28 以上より、次のような状態であることがわかる。
29. スライド　29 １０−４．PとNP完全
30. スライド　30 似ているクラスPの問題とNP完全の問題１
31. スライド　31 a
32. スライド　32 似ているクラスPの問題とNP完全の問題２
33. スライド　33 スライド33
34. スライド　34 似ているクラスPの問題とNP完全の問題3
35. スライド　35 スライド35