コンピューターに問題を解かせるときに、それがどの程度の時間を消費するのかも大きな問題です。この観点から、問題はいくつかのパターンに区分されています。ただし、ややこしいです。
#おことわり
なお、分かりやすさを優先して、厳密でない説明となっている部分があります。たとえば、チューリング完全性を前提に、チューリング機械で計算するものを、通常のコンピューターで計算するものとしています。
P
ある判定問題（yes/noで答えられる問題）があって、それを解くことのできる多項式時間アルゴリズム（問題の規模に対して、計算時間が規模の多項式で表現される上限を持つ）が存在する場合に、その問題は「Pに属する」ということになります。
なお、この定義にはいくつかの注意点があります。まず、yes/noで答えられない問題（配列のソート）などは、定義上Pには分類されません。また、定数時間の場合や、問題規模の対数で多項式になる場合など、$O(n)$より小さい場合でも、Pに区分されます。さらに、「問題規模」の取り方には任意性があって、たとえば素数判定問題では入力値の「桁数」を問題の大きさとするのが主流です（入力値自体を大きさとすると、$O(n)$以下であることは自明なので議論が深まりません）。
たとえ多項式時間アルゴリズムがあっても、次数や定数項が大きいなどで、実用的なサイズの問題にはそうでないアルゴリズムのほうが速い、というケースもありますが、あくまで多項式かどうかで区分します。
NP
NPには、2通りの定義がありますが、どちらも本質的には同じものです。
- ランダム性を持った多項式時間アルゴリズムがあって、運がよければyesの結果を返す判定問題。
- ある問題とそれがyesになる証拠があった場合に、本当に成立しているかどうか多項式時間で検証できる問題。
NPはNon-deterministic P（非決定的多項式時間）の略で、Not Pという意味ではありません（2. より、そもそも多項式時間で解けるP問題はNPにも含まれます）。また、これも判定問題以外はNPに含まれません。
NP完全
上でP問題もNP問題に含まれるといったように、同じ「NP」といっても難易度の違う1いくつかの問題が存在していますが、このNPの中には、同じNPの中にある任意の問題を多項式時間で変形することで、その問題に変形することができる問題があります。つまりはこの問題がNPの中でいちばんむずかしい（これが解ければNPの問題はすべて解ける）ということになりますが、そういった問題をNP完全問題といいます。
「いちばん」とは言いましたが、NP完全問題は多数発見されています（それぞれ同士を多項式時間で変換できるものであれば、すべてがNP完全です）。
- ハミルトン閉路問題（頂点を辺でつないたグラフで、すべての頂点を1回ずつ回る閉路があるかの判定問題）
- 部分和問題（整数の組に対して、その中からいくつか抜き出して特定の数を作れるかという判定問題）
- ぷよぷよ（与えられたぷよの組とフィールドに対して、特定の数の連鎖を組めるかという判定問題）
- テトリス（与えられたテトリスの組とフィールドに対して、特定の列数だけ消すことができるかという判定問題）
NP困難
NPに関連する区分として「NP困難」というものがあります。これは、以下の条件を満たすものです。
- 判定問題以外の問題でも構わない
- その問題自身がNPに属するかは問わない
- 多項式時間ですべてのNP問題（実質、どれか1つのNP完全問題）をその問題に帰着できる
有名な「巡回セールスマン問題」も、「これ自体が判定問題でない」「ハミルトン閉路問題から容易に変換できる」ということで、NP困難問題に区分されます（判定問題でないので、NPでもNP完全でもありません）。
さらに言えば、「チューリングマシンの停止問題」という決定不能な問題もNP困難に属します。適当なNP完全問題について「解ければ終了、解けなければ無限ループ」というようなプログラムを書いて、これを停止性問題として判定すれば、NP完全問題も解けるからです。
まとめ
NP完全なものはNPかつNP困難なものです。また、NPにはNP完全やPが含まれますが、この3つは判定問題だけが属するものです。けっこう混同されることが多いので、よく知った上で峻別しましょう。
-
多項式時間で解けないNP問題があるという見方も強いですが、証明はされていません。 ↩