P、NP、NP困難の概念
計算困難性の理論では、この世界の問題にはその計算の複雑さに応じて３つのクラスに分かれる。
- Pクラス
- NPクラス
- NP困難クラス
正確にはNP完全というクラスもあるが、正確さを期すことが目的ではないので、省略する。
ここで、Pとは、多項式時間（Polylogarithmic time）の頭文字である。
（正直、Wikipediaで読んだのだが、話がややこしい上に、正しいのかどうかもよく分からん。今度、情報のTAやった先生にメールででも聞いてみよう）
あるデータサイズnの問題が与えられたとき、計算にかかる時間（もしくは計算に必要なステップ数）が、n, n log n, n^10のようなオーダーになるとき、これらを多項式時間のクラスという。
大雑把に言うと、
問題の答えを求めるのに必要な時間が多項式時間以下のものをP、
問題に解が与えられたとき、その解の真偽を判定するのに必要な時間が多項式時間以下であるものをNP
と呼ぶ。
多項式時間で答えが求まる問題であれば、解の真偽を判定するのに必要な時間は、それよりも小さいので、PはNPに含まれることは自明である。（P⊆NP）
が、PはNPの部分集合に過ぎない、つまり与えられた解の真偽は多項式時間で判定できるが、解を求めるには多項式時間で収まらないような問題が存在すると予測されている。（P≠NP予想）
例を上げると、インターネットの暗号通信の基盤となっている公開鍵暗号では、素因数分解が使われているのは有名な話だろう。これは、二つの巨大な素数の積を求めることは簡単だが、逆に二つの巨大な素数の積を、もとの素数に素因数分解することが容易ではないことを利用している。
素数をそれぞれ、p,qとしその積をNとする（N=pq）
この問題の場合、前もって素数であることが分かっているpとqから、Nを求めるのは極めて、容易である。（これはPクラスの問題）。また「p×q=N」という命題の真偽を判定するのも多項式時間内で終了する。つまりこの掛け算は、PクラスでありかつNPクラスである問題である。
ところが、Nの素因数分解は様子が違ってくる。
「Nの素因数は、pである」と言う命題の真偽を確かめるのも容易である（NPクラスの問題）。だが、「Nの二つの素因数は何か？」これは極めて難しく、有限時間で上手く解くアルゴリズムは見つかっていない。つまり、Nの素因数分解は、NPクラスではあるが、Pクラスではない。これが有名な「P≠NP予想」の内容である。
NP困難なクラスとは、NPよりもさらに難しく、与えられた解の真偽でさえ多項式時間以内に判定できない問題クラスをいう。非線形で内容が判らないような関数の最適化問題がこのクラスに該当する。「最適値を求めよ」は計算不可能、さらに「最適値はXである」と言う命題の真偽判定すら、多項式時間では終わらない。NPクラスよりもさらに困難である、という意味でNP困難と呼ばれる。
こういう問題に挑むために、近似解探索戦略（メタヒューリスティクス）が研究されている。
・山登り法
・遺伝的アルゴリズム
・タブーサーチ
・焼きなまし法
・シミュレーティッドエヴェリューション
etc...
どのメタヒューリスティクスが探索に適しているかは、問題に大きく依存する。
