| クラスNP |
|
|
|
|
|
|
|
|
|
|
| • | 答えがYESである証拠が多項式時間で確認 |
||||||||
| できる決定問題 |
|||||||||
| • | 例：（決定問題） |
||||||||
| 22時間以内に終了する加工順序はある？ |
|||||||||
| • | (証拠)加工順序を１つ示す |
||||||||
| クラスNPに属する |
|
|
|
|
|
| ORの問題の |
||||
| (決定問題版)は |
||||
| ほぼクラスNP |
||||
|
|
|
| 総当り法(素朴な方法)で理論的には解け |
||
| る決定問題は，ほとんどクラスNPに属す |
||