指数時間アルゴリズムと多項式時間アルゴリズム

ここまで、完結にまとめて答えられていると分かりやすくて頭に入りやすかった。

http://www.fjt.info.gifu-u.ac.jp/~hara/algo1/no.5/tsld012.htm
より引用

• n, n2, n3などのような時間計算量が多項式であらわされるようなアルゴリズムを多項式時間アルゴリズムという
• 2n, n!などのようなnの指数関数であらわれるアルゴリズムを指数時間アルゴリズムという

http://www.fjt.info.gifu-u.ac.jp/~hara/algo1/no.5/tsld013.htm
より引用

NP完全問題
指数時間アルゴリズムは得られているが，多項式時間アルゴリズムは多分存在しないだろうと予測されている問題のこと．

NP = non-deterministic polynomal