完備 (複雜度)

在計算複雜性理論內，一個計算問題（computational problem）對一個複雜度類是完備或者完全的，用比較不正式的解釋，是說這問題在此複雜度類裡面是一個「最難的」或者「最代表性的」題目。如果一個問題的解法可以允許你快速解決這個複雜度類的其他問題的話，我們說這問題對此類別是難（hard）的題目。

更正式的說法是，如果在一個給定的歸約方式之下，所有複雜度類C裡面的問題都存在某種歸約方式，可以歸約到某個問題p，我們說這個問題p是C的難問題。如果一個問題是此類別的，且本身是這個類別裡面的一員，則這個問題就是對這個複雜度類完備的（在給定的歸約條件之下）。

一個問題如果對複雜度類C是完備的話，我們會說這個問題是C-完備或者C完全（C-complete）的問題，至於這一些對C是完備問題的集合我們也稱為C-完備。第一個且是最有名的是NP完全：一個包含許多實際但是不容易的題目。相同的，我們習慣用C難（C-hard）這種用詞稱呼包含所有C難（C-hard）的問題，例如說，NP難。

正常來說我們都假設歸約過程在計算複雜度上面不會比起問題本身要難。因此之故，如果我們對一個C-完備問題有「計算上簡單」的解法的話，則所有在「C」這類別裡面的問題都有「簡單」的解法。

一般說來，有遞歸可枚舉（recursive enumeration）的複雜度類都會有已知的完備問題，而並非如此的類別則沒有已知的完備問題。舉例來說，NP、反NP、PLS、PPA都有已知的完備問題，而RP、ZPP、BPP和TFNP則沒有已知的完備問題（雖然這不代表未來不會發現完備問題）。

有一些複雜度類是沒有完備問題存在的。舉例來說，Sipser證明了存在一個語言M令BPP^M（BPP加上一個M的諭示）是沒有完備問題的^[1]。

參考資料

1. M. Sipser. On relativization and the existence of complete sets, Proceedings of ICALP'82, Springer-Verlag Lecture Notes in Computer Science volume 140, pp. 523-531, 1982.