完備 (複雜度) 在計算複雜性理論內一個計算問題computational problem對一個複雜度類是完備或者完全的用比較不正式的解釋是說這問題在此複雜度類裡面是一個最難的或者最代表性的題目如果一個問題的解法可以允許你快速解決這個複雜度類的其他問題的話我們說這問題對此類別是難hard的題目 更正式的說法是如果在一個給定的歸約方式之下所有複雜度類C裡面的問題都存在某種歸約方式可以歸約到某個問題p我們說這個問題p是C的難問題如果一個問題是此類別的且本身是這個類別裡面的一員則這個問題就是對這個複雜度類完備的在給定的歸約條件之下 一個問題如果對複雜度類C是完備的話我們會說這個問題是C完備或者C完全Ccomplete的問題至於這一些對C是完備問題的集合我們也稱為C完備第一個且是最有名的是NP完全一個包含許多實際但是不容易的題目相同的我們習慣用C難Chard這種用詞稱呼包含所有C難Chard的問題例如說NP難 正常來說我們都假設歸約過程在計算複雜度上面不會比起問題本身要難因此之故如果我們對一個C完備問題有計算上簡單的解法的話則所有在C這類別裡面的問題都有簡單的解法 一般說來有遞歸可枚舉recursive enumeration的複雜度類都會有已知的完備問題而並非如此的類別則沒有已知的完備問題舉例來說NP反NPPLSPPA都有已知的完備問題而RPZPPBPP和TFNP則沒有已知的完備問題雖然這不代表未來不會發現完備問題 有一些複雜度類是沒有完備問題存在的舉例來說Sipser證明了存在一個語言M令BPPMBPP加上一個M的諭示是沒有完備問題的