完全性（複雑性）

計算複雑性理論において、ある計算問題が複雑性クラスに対して完全であるとは、技術的な意味で、その複雑性クラスの中で「最も難しい」（あるいは「最も表現力豊かな」）問題の一つである場合をいう。

より厳密に言えば、問題pは、ある種類の還元法の下で複雑性クラスCに対して困難であるとは、 C内の任意の問題からpへの還元法（その種類の還元法）が存在する場合をいう。問題がそのクラスに対して困難であり、かつそのクラスのメンバーである場合、その問題はそのクラス（その種類の還元法）に対して完全である。

クラスCに対して完全な問題はC-完全であると言われ、 Cに対して完全なすべての問題のクラスはC-完全と表記されます。最初に定義され、最もよく知られている完全なクラスはNP-完全であり、これは実際に発生する多くの解決困難な問題を含むクラスです。同様に、クラスCに対して難しい問題はC-困難と呼ばれ、例えばNP-困難などがあります。

通常、問題となっている削減の計算複雑度は、クラス自体の計算複雑度よりも高くないと想定されます。したがって、C完全問題に「計算的に容易な」解が存在するならば、「C」に含まれるすべての問題には「容易な」解が存在すると言えるでしょう。

一般的に、計算可能な列挙を持つ複雑性クラスには既知の完全問題が存在するのに対し、計算可能な列挙を持たないクラスにはそのような問題は存在しない。例えば、NP、co-NP、PLS、PPAはいずれも既知の自然完全問題を持つ。

完全な問題を持たないクラスが存在する。例えば、Sipserは、BPP ^M（オラクルMを持つBPP）に完全な問題が存在しないような言語Mが存在することを示した。^{[ 1 ]}