完了（複雑さ）

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

より正式には、問題p が、与えられたタイプの還元の下で複雑性クラスCに対して困難であるとは、 C内の任意の問題からpへの（与えられたタイプの）還元が存在する場合を指します。問題がクラスとそのクラスのメンバーの両方に対して困難である場合、その問題はそのクラスに対して（そのタイプの還元に対して） 完全です。

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

通常、問題の削減はクラス自体よりも計算の複雑さが高くないと想定されます。したがって、C 完全な問題に「計算上簡単な」解決策がある場合、「C」のすべての問題には「簡単な」解決策があると言えます。

一般的に、再帰列挙を持つ複雑性クラスには既知の完全問題がありますが、再帰列挙を持たないクラスには完全な問題はありません。たとえば、NP、co-NP、PLS、PPA はすべて既知の自然完全問題を持っています。

完全問題のないクラスも存在する。例えば、Sipserは、BPP ^M（BPP with oracle M ）に完全問題がない言語Mが存在することを示した。 ^[1]