NPのソースを表示

{{Otheruses|計算量}}

[[計算複雑性理論]]における '''NP''' ({{Lang-en-short|Non-deterministic Polynomial time}})は、[[複雑性クラス]]のひとつであり、答えがyesとなるような問いに対して、多項式時間で検証できる証拠が存在する決定問題のクラスである。

== 定義 ==
'''NP''' は、'''[[NTIME]]'''を使って次のように定義される<ref>{{cite book
 |title=Introduction to the Theory of Computation
 |first=Michael|last=Sipser
 |publisher=Cengage Learning
 |isbn=978-1133187790
 |edition=3
 |date=2012-06-27}}</ref>。

:<math>\textsf{NP} = \bigcup_{k\in\mathbb{N}} \textsf{NTIME}(n^k)</math>

つまり、[[非決定性チューリングマシン]]によって[[多項式時間]]で解ける[[決定問題]]のクラスであり、名称も {{Lang-en-short|Non-deterministic Polynomial time|}}（非決定性多項式時間）の略である。また、多項式時間検証可能という[[同値]]な定義もある。言語 <math>L</math> が '''NP''' に属するとは、多項式時間決定性[[チューリングマシン]] <math>M</math> と多項式 <math>p</math> が存在し、次の性質を満たすことを言う。

*<math>x\in L</math>ならば、ある証拠 <math>w \in \{0, 1\}^{p(|x|)}</math> が存在し、<math>M(x, w) = 1</math>
*<math>x\not\in L</math>ならば、どんな証拠 <math>w \in \{0, 1\}^{p(|x|)}</math> でも、<math>M(x, w) = 0</math>

== 例 ==
[[ハミルトン閉路問題]]は、「与えられたグラフについて、全ての頂点を一度だけ通る閉路(ハミルトン閉路)が存在するか」という問題である。そのような閉路が与えられれば、yesであること(つまり、「本当に全ての点を一度ずつ通っているか」)は多項式時間で検証できるから、これが証拠と言えるため、ハミルトン閉路問題は '''NP''' に属する。証拠を具体的に求める計算量などを考える必要がなく、ただ「存在すること」が要求されることに注意する。また、noであった場合は、どんな証拠であっても検証時に間違ってハミルトン閉路であるとはならないことも重要である。

合成数判定問題は因数が証拠となるため、'''NP'''に属することがすぐさま分かるが、その補問題の素数判定問題ではそのような直感的で分かりやすい証拠が知られていない。[[整数論]]によれば、<math>p-1</math> の完全な素因数分解と原始根が与えられれば、奇数 <math>p</math> が素数であることを多項式時間で検証できる。ということは、素数であるという証拠は、<math>p-1</math> の素因数分解と原始根で足りるかというと厳密にはそうではない。 <math>p-1</math> の素因数分解が本当にすべて素因数に分解されているか、ということを検証しなければならないからである。幸いにも、再帰的に素数判定の検証を行うことによって、全体として <math>p</math> が素数であることを多項式時間で検証できる。以上より、素数判定問題は'''NP'''に属する。合成数判定問題の結果と併せると <math>\textsf{NP}\cap\textsf{co-NP}</math> に属することが言える。なお、現在では素数判定問題は '''P''' に属することが証明されている<ref>{{cite journal
 |first=Manindra |last=Agrawal |authorlink=マニンドラ・アグラワル
 |first2=Neeraj |last2=Kayal |authorlink2=ニラジュ・カヤル
 |first3=Nitin |last3=Saxena
 |url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
 |title=PRIMES is in P
 |journal=Annals of Mathematics
 |volume=160
 |year=2004
 |issue=2
 |pages=781–793
 |doi=10.4007/annals.2004.160.781
 |jstor=3597229 }}</ref>。

'''NP''' に属するが、 '''P''' に属することが証明されていない問題の多くは '''NP'''完全であり、その例は「[[NP完全問題]]」の項に譲る。それ以外の、 '''P''' にも '''NP'''完全にも属さない問題の候補として{{仮リンク|グラフ同型性判定問題|en|Graph isomorphism problem}}が挙げられる。

== 関連する複雑性クラス ==
=== 多項式階層 ===
[[Image:Polynomial time hierarchy.svg|250px|thumb|right|多項式階層の包含関係図]]
'''[[P (計算複雑性理論)|P]]'''は、決定性チューリングマシンを使って多項式時間で解ける問題のクラスである。定義より明らかに <math>\textsf{P} \subseteq \textsf{NP}</math> だが、 <math>\textsf{P} \neq \textsf{NP}</math> かどうかは未解決問題である([[P≠NP予想]])。また '''[[co-NP]]''' は、 '''NP''' の補問題のクラスである。つまり、
:<math>\textsf{co-NP} = \{\bar{L} | L \in \textsf{NP} \}</math>
というクラスである。

これらクラスと '''NP''' は[[多項式階層]]を構成する。<math>\textsf{P} = \Sigma_0^{\rm P} = \Pi_0^{\rm P}</math>とし、適切に定義することによって、
:<math>\Sigma_0^{\rm P} \subseteq \Sigma_1^{\rm P} \subseteq \ldots</math>
:<math>\Pi_0^{\rm P} \subseteq \Pi_1^{\rm P} \subseteq \ldots</math>
という階層を成し、全クラスの和集合を '''PH''' とする。このとき、 <math>\textsf{NP} = \Sigma_1^{\rm P}</math>、 <math> \textsf{co-NP} = \Pi_1^{\rm P} </math> である。ある ''k'' について <math>\Sigma_k^{\rm P} = \Sigma_{k+1}^{\rm P}</math> すなわち <math>\Sigma_k^{\rm P} = \Pi_{k}^{\rm P}</math> となることを「多項式階層が第 ''k'' 層で潰れる」と言うが、
*もし <math>\textsf{P} = \textsf{NP}</math> なら、階層は完全に潰れ、 <math>\textsf{NP} = \textsf{co-NP} = \textsf{PH}</math>。
*もし <math>\textsf{NP} = \textsf{co-NP}</math> なら、階層が第1層で潰れ、 <math>\textsf{NP} = \textsf{PH}</math>。
つまりP≠NP予想は、多項式階層で考えると「完全には潰れない」という予想に換言できる。多項式階層は、すべての階層で潰れないと考えられているが、未解決問題である。

=== NP完全およびNP困難 ===
'''[[NP完全問題|NP完全]]'''と'''[[NP困難]]'''は、'''NP'''の完全問題と困難問題のクラスである。直感的には、NPに属する任意の問題と少なくとも同じくらい難しい問題を[[NP困難]]であるといい、そのうちNPに属するものをNP完全問題という。これらの概念は正確には[[多項式時間帰着]]を使って定義する。[[充足可能性問題]]が'''NP'''完全に属することが知られている({{仮リンク|クック–レビンの定理|en|Cook–Levin theorem}})。'''NP'''完全問題の1つでも '''P''' に属することが証明できれば '''P'''='''NP''' と言えるが、そのような問題は見つかっていない。

=== NEXPTIMEとEXPSPACE ===
'''[[NEXPTIME]]'''は、非決定性チューリングマシンを使って指数時間で解ける問題のクラスであり、{{仮リンク|時間階層定理|en|Time hierarchy theorem}}より <math>\textsf{NP} \subsetneq \textsf{NEXPTIME}</math> が言える。また、'''[[EXPSPACE]]'''は、決定性チューリングマシンの指数サイズの領域を使って解ける問題のクラスであり、{{仮リンク|領域階層定理|en|Space hierarchy theorem}}より <math>\textsf{NP} \subsetneq \textsf{EXPSPACE}</math> が言える。

=== 対話証明系 ===
多項式時間検証可能という側面から '''NP''' を考えると、対話証明とみなすこともできる。'''[[Arthur–Merlinプロトコル|AM]]'''は('''P''' を '''BPP''' に拡張したように) '''NP''' から確率的な挙動を許すようにしたクラスである。{{仮リンク|PCP定理|en|PCP theorem}}は、<math>\textsf{NP} = \textsf{PCP}(O(\log n), O(1))</math> を示している。

== 関連項目 ==
* [[複雑性クラス]]
** [[co-NP]]
** [[NP完全問題|NP完全]]
** [[NP困難]]
* [[P≠NP予想]]

== 外部リンク ==
* [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#np Complexity Zoo NP]

== 参考文献 ==
{{reflist}}

{{複雑性クラス}}

[[Category:計算複雑性理論]]
[[Category:数学に関する記事]]