NP

NP（非決定性多項式時間）とは

計算複雑性理論において、NP（Non-deterministic Polynomial time）は、重要な複雑性クラスの一つです。これは、ある問題に対する答えが「はい」である場合に、その答えを多項式時間で検証できるような証拠が存在する決定問題の集合を指します。言い換えれば、問題の解を「推測」することができた場合、その推測が正しいかどうかを効率的に確認できる問題のクラスです。

定義

NPは、非決定性チューリングマシン（NTIME）を用いて、次のように定義されます。

math
{\textsf {NP}}=\bigcup _{k\in \mathbb {N} }{\textsf {NTIME}}(n^{k})


ここで、\(n\) は入力のサイズを表し、\(k\) は任意の自然数です。この定義から、NPは、非決定性チューリングマシンによって多項式時間で解ける問題のクラスであることがわかります。

NPに属する言語 \(L\) は、以下の条件を満たす多項式時間決定性チューリングマシン \(M\) と多項式 \(p\) が存在します。

1. 入力 \(x\) が \(L\) に属する場合、\(M(x, w) = 1\) となるような証拠 \(w\) が存在します。ここで、証拠 \(w\) の長さは、入力サイズ \(|x|\) の多項式 \(p(|x|)\) で制限されます。
2. 入力 \(x\) が \(L\) に属さない場合、いかなる証拠 \(w\) を用いても \(M(x, w) = 0\) となります。

例

ハミルトン閉路問題は、NPに属する代表的な例です。この問題は、与えられたグラフにおいて、すべての頂点を一度だけ通る閉路が存在するかどうかを判定するものです。もし、そのような閉路が与えられた場合、その閉路が本当にすべての頂点を一度だけ通っているかどうかを多項式時間で検証できます。したがって、ハミルトン閉路問題はNPに属します。

合成数判定問題もNPに属します。合成数の場合、その因数が証拠となり、多項式時間で検証可能です。一方、素数判定問題では、直感的な証拠がすぐには見つかりませんが、素数であることの証拠を再帰的に検証することで、多項式時間で検証可能であることが知られています。したがって、素数判定問題もNPに属し、合成数判定問題と合わせて、NPとco-NPの共通部分に属すると言えます。現在では、素数判定問題はPに属することが証明されています。

P, NP, co-NPの関係

Pは、決定性チューリングマシンによって多項式時間で解ける問題のクラスです。定義から、\(P \subseteq NP\) であることは明らかですが、\(P
eq NP\) かどうかは未解決の問題です（P≠NP予想）。

co-NPは、NPの補問題のクラスであり、NPに属する問題の否定版が含まれます。つまり、言語 \(L\) がNPに属する場合、\(L\) の補集合はco-NPに属します。

これらのクラスは、多項式階層を構成します。\(P = \Sigma_0^P = \Pi_0^P\) と定義すると、

math
\Sigma_0^P \subseteq \Sigma_1^P \subseteq \ldots

math
\Pi_0^P \subseteq \Pi_1^P \subseteq \ldots


という階層が形成されます。ここで、\(NP = \Sigma_1^P\) と \(co\text{-}NP = \Pi_1^P\) です。もし、\(P = NP\) ならば、階層は完全に潰れ、\(NP = co\text{-}NP = PH\) となります。また、\(NP = co\text{-}NP\) ならば、階層は第1層で潰れ、\(NP = PH\) となります。P≠NP予想は、この階層が完全に潰れないという予想に換言できます。

NP完全とNP困難

NP完全は、NPに属する問題の中で最も難しい問題のクラスです。NP困難は、NPに属する任意の問題と少なくとも同じくらい難しい問題のクラスであり、NPに属するものをNP完全問題といいます。これらの概念は、多項式時間帰着を用いて定義されます。充足可能性問題がNP完全に属することが知られており（クック–レビンの定理）、NP完全問題のいずれか一つでもPに属することが証明されれば、P=NPとなることが知られています。

NPと他の複雑性クラスの関係

NEXPTIMEは、非決定性チューリングマシンを使って指数時間で解ける問題のクラスであり、時間階層定理より \(NP \subsetneq NEXPTIME\) が成立します。また、EXPSPACEは、決定性チューリングマシンで指数サイズの領域を使って解ける問題のクラスであり、領域階層定理より \(NP \subsetneq EXPSPACE\) が成立します。

対話証明系

多項式時間検証可能という側面からNPを見ると、対話証明としても解釈できます。AMは、PをBPPに拡張したように、NPから確率的な挙動を許容するように拡張したクラスです。PCP定理は、

math
{\textsf {NP}}={\textsf {PCP}}(O(\log n),O(1))


を示しています。

関連項目

複雑性クラス
co-NP
NP完全
NP困難
* P≠NP予想

NPは計算複雑性理論における重要な概念であり、多くの研究が行われています。P≠NP予想は、計算機科学における最も重要な未解決問題の一つであり、その解決は様々な分野に大きな影響を与えると考えられています。

もう一度検索