PおよびNPとの関係

ウィキペディア小見出し辞書

PおよびNPとの関係

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 03:55 UTC 版)

「RP (計算複雑性理論)」の記事における「PおよびNPとの関係」の解説

P は RP の部分集合であり、RP は NP の部分集合である。同様に、P は Co-RP の部分集合であり、Co-RP は Co-NP の部分集合である。これらの包含関係が真部分集合の関係であるかどうかは未だわかっていない。しかし、一般に P ≠ RP または RP ≠ NP であろうと考えられており、そうでないと P = NP ということになってしまい、これは一般には偽と考えられている（P≠NP予想）。RP = Co-RP であるかどうかも未だ明らかになっていないし、RP が NP と Co-NP の積集合の部分集合かどうかも明らかでない。 Co-RP に属する問題のうち、P に属さないと思われている問題の例として、整数に関する多変量計算式がゼロ多項式かどうかの判定問題がある。例えば、"x*x - y*y - (x+y)*(x-y)" はゼロ多項式だが、"x*x + y*y" はゼロ多項式ではない。 場合によってはより便利と思われる RP の定式化として、少なくともある(入力長に依らない)一定の割合の計算経路群が受理する場合に限って機械全体としてその入力を受理する非決定性チューリング機械が認識できる問題の集合という定義がある。一方、NP は少なくとも一つの計算経路だけが受理すればよいのであって、その割合は指数関数的に小さい。このように定式化すると、RP が NP の部分集合であることがより明確化される。