完备 (复杂度)

在计算复杂性理论内，一个计算问题（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的谕示）是没有完备问题的。