| クラスPとクラスNPとNP完全問題 |
|
|
|
|
|
|
|
|
|
| TSP |
||||||||
| ナップサック問題 |
||||||||
| 集合分割問題 |
||||||||
| 最適加工順序問題 |
||||||||
| 等多数 |
||||||||
| NP完全問題 |
|
|
|
|
|
|
|
| NP完全問題は |
||||||
| （今のところ） |
||||||
| 多項式時間解法が |
||||||
| 無い問題なんだ． |
||||||
|
|
|
|
|
|
| NP完全問題かク |
|||||
| ラスPに属すのか |
|||||
| 判別できていない |
|||||
| 問題もたくさんある |
|||||
| クラスNP |
| クラスP |
|
|
|
|
|
| 最短路問題 |
||||
| 最大流問題 |
||||
| ソーティング |
||||
| 等多数 |
||||