| クラスNPでの大発見 |
| Karp博士の発見（1972年）の大雑把な解釈 |
|
|
|
| クラスNPに属するすべての問題はTSP（の決定問題）に |
||
| 簡単に（多項式時間の手間で）変形可能 |
||
| 更なる事実 |
| TSP⇔ナップサック問題 |
|
|
|
| TSPはクラスNPに属する問題の中で |
||
| 最も難しい |
||
| TSP⇔集合分割問題 |
|
|
|
| 両者は同じ |
||
| 位難しい |
||
|
|
|
|
|
| TSPに対して多項式時間解法があれば， |
||||
| クラスNPに属する問題は |
||||
| すべて多項式時間で解ける |
||||
| NP完全問題 |