学生の備忘録なブログ

日々のことを忘れないためのブログです。一日一成果物も目標。技術系はQiitaにあげるように変更しました。

NP困難問題

NP困難問題とは

よく聞くけど,よくわからないやつ,NPとか,今回理解することができたので,ここにまとめます.

用語について

大雑把に言うと,

Pとは一般的な解法で解けること.

P,NP

例えば, 2次方程式は『解の公式』の解は求められる.

一般的な解法があるものはあらかじめ計算にどれくらいの時間がかかるのか見積もることが出来る。

これを「多項式時間(Ploymonial-time)で解ける」という。

しかし,そうではない問題もありますよね?

 これに対して「素因数分解」や「ナップサック問題」のような問題は決定的な解法が知られておらず,考えられるすべての場合をしらみつぶしに調べなければならない。

 このような問題を「多項式時間で解けない(Nondeterministic Polynomial-time)」といいます。

NP困難

 そこで P 問題(Polynomial つまり多項式時間で解ける問題)と NP 問題(Nondeterministic Polynomial つまり多項式時間で解けない問題)については

P≠NP (世の中には一般的な解法がある問題と,総当たりでしらみつぶしに調べるより他に手がない問題と二通りある)

P=NP (一生懸命考えればどんな問題でも一般的な解法があるはず) という分類のされ方をします.これらは将来,明確な解が見つかるかもしれない,という前提がある.

まとめ

多項式時間(計算量が分かっている問題を解くためにかかる時間) P(多項式時間で解ける) NP(多項式時間で解けない)

参考

ナップサック問題