NP

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

定義

NP は、NTIMEを使って次のように定義される^[1]。

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

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

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

例

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

合成数判定問題は因数が証拠となるため、NPに属することがすぐさま分かるが、その補問題の素数判定問題ではそのような直感的で分かりやすい証拠が知られていない。整数論によれば、 $p-1$ の完全な素因数分解と原始根が与えられれば、奇数 $p$ が素数であることを多項式時間で検証できる。ということは、素数であるという証拠は、 $p-1$ の素因数分解と原始根で足りるかというと厳密にはそうではない。 $p-1$ の素因数分解が本当にすべて素因数に分解されているか、ということを検証しなければならないからである。幸いにも、再帰的に素数判定の検証を行うことによって、全体として $p$ が素数であることを多項式時間で検証できる。以上より、素数判定問題はNPに属する。合成数判定問題の結果と併せると ${\textsf {NP}}\cap {\textsf {co-NP}}$ に属することが言える。なお、現在では素数判定問題は P に属することが証明されている^[2]。

NP に属するが、 P に属することが証明されていない問題の多くは NP完全であり、その例は「NP完全問題」の項に譲る。それ以外の、 P にも NP完全にも属さない問題の候補としてグラフ同型性判定問題（英語版）が挙げられる。

関連する複雑性クラス

多項式階層

Pは、決定性チューリングマシンを使って多項式時間で解ける問題のクラスである。定義より明らかに ${\textsf {P}}\subseteq {\textsf {NP}}$ だが、 ${\textsf {P}}\neq {\textsf {NP}}$ かどうかは未解決問題である(P≠NP予想)。また co-NP は、 NP の補問題のクラスである。つまり、

{\textsf {co-NP}}=\{{\bar {L}}|L\in {\textsf {NP}}\}

というクラスである。

これらクラスと NP は多項式階層を構成する。 ${\textsf {P}}=\Sigma _{0}^{\rm {P}}=\Pi _{0}^{\rm {P}}$ とし、適切に定義することによって、

\Sigma _{0}^{\rm {P}}\subseteq \Sigma _{1}^{\rm {P}}\subseteq \ldots

\Pi _{0}^{\rm {P}}\subseteq \Pi _{1}^{\rm {P}}\subseteq \ldots

という階層を成し、全クラスの和集合を PH とする。このとき、 ${\textsf {NP}}=\Sigma _{1}^{\rm {P}}$ 、 ${\textsf {co-NP}}=\Pi _{1}^{\rm {P}}$ である。ある k について $\Sigma _{k}^{\rm {P}}=\Sigma _{k+1}^{\rm {P}}$ すなわち $\Sigma _{k}^{\rm {P}}=\Pi _{k}^{\rm {P}}$ となることを「多項式階層が第 k 層で潰れる」と言うが、

もし ${\textsf {P}}={\textsf {NP}}$ なら、階層は完全に潰れ、 ${\textsf {NP}}={\textsf {co-NP}}={\textsf {PH}}$ 。
もし ${\textsf {NP}}={\textsf {co-NP}}$ なら、階層が第1層で潰れ、 ${\textsf {NP}}={\textsf {PH}}$ 。

つまりP≠NP予想は、多項式階層で考えると「完全には潰れない」という予想に換言できる。多項式階層は、すべての階層で潰れないと考えられているが、未解決問題である。

NP完全およびNP困難

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

NEXPTIMEとEXPSPACE

NEXPTIMEは、非決定性チューリングマシンを使って指数時間で解ける問題のクラスであり、時間階層定理（英語版）より ${\textsf {NP}}\subsetneq {\textsf {NEXPTIME}}$ が言える。また、EXPSPACEは、決定性チューリングマシンの指数サイズの領域を使って解ける問題のクラスであり、領域階層定理（英語版）より ${\textsf {NP}}\subsetneq {\textsf {EXPSPACE}}$ が言える。

対話証明系

多項式時間検証可能という側面から NP を考えると、対話証明とみなすこともできる。AMは(P を BPP に拡張したように) NP から確率的な挙動を許すようにしたクラスである。PCP定理（英語版）は、 ${\textsf {NP}}={\textsf {PCP}}(O(\log n),O(1))$ を示している。

外部リンク

Complexity Zoo NP

参考文献

^ Sipser, Michael (2012-06-27). Introduction to the Theory of Computation (3 ed.). Cengage Learning. ISBN 978-1133187790
^ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). “PRIMES is in P”. Annals of Mathematics 160 (2): 781–793. doi:10.4007/annals.2004.160.781. JSTOR 3597229.

[1] Sipser, Michael (2012-06-27). Introduction to the Theory of Computation (3 ed.). Cengage Learning. ISBN 978-1133187790

[2] Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). “PRIMES is in P”. Annals of Mathematics 160 (2): 781–793. doi:10.4007/annals.2004.160.781. JSTOR 3597229.

[1]

[2]

表話編歴主な複雑性クラス
実用的な時間で解けるクラス	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P完全 ZPP RP BPP BQP APX
実用的な時間で解けないと疑われているクラス	UP NP NP完全 NP困難 co-NP co-NP完全 AM QMA PH ⊕P PP #P #P完全 IP PSPACE
実用的な時間では解けないクラス	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL
クラス階層	多項式階層指数階層グジェゴルチク階層算術的階層ブーリアン階層
クラスの族	DTIME NTIME DSPACE NSPACE PCP 対話型証明系
一覧・カテゴリ

定義

例