|
|
|
| 多項式時間アルゴリズム |
||
| (polynomial-time
algorithm) |
||
|
|
|
|
| • | 入力サイズ：n |
||
| • | 多項式：f(n)=aknk+ak-1nk-1+…+a1n+a0 |
||
| • | 最悪計算量がO(f(n)) |
||
| 多項式時間アルゴリズムが存在する問題の集まり⇒クラスP |
| 知識力勝負 |
|
|
|
| ある問題がクラスPに |
||
| 属すか確かめたい |
||
| アイディア勝負 |
|
|
|
| クラスPに属す←解法を提案する・探す |
||
| クラスPに属さない←どうやって示す？ |
||
| 難しい作業 |