NP-Completeness : Note on Algorithms16時間 このように、nの増加にしたがって、計算時間が増加するが、nが十分大きいと、 多項式時間よりも、指数関数時間のほうが必ず大きくなる。 つまり、小さな問題では、どちらが早く問題を解くかは、 あまり問題にならないことが多いが、(0.001秒 vs. 0.0012秒とか) 大きな問題では、多項式時間の方が早く問題を解くのである。 また、多くの研究者が開発している多項式時間アルゴリズムは、計算時間が O(n2)とか、O(n3)とか、O(n2log n)とかであり、 指数部の定数は3以下であることがほとんどであり、 O(n10)とかは、まずない。このような意味でも多項式時間アルゴリズム は高速なのである。 判定問題 問題には、いくつかの種類がある。 判定問題 答はYesかNOかのどちらか 例 グラフGと2点u,vと定数kが与えられたとき、u,v間に長さk以下の 道があるか? 最適化問題(Op
