近似的困难性

计算机科学中，近似的复杂性（hardness of approximation）是研究最佳化问题中，有关寻找接近最佳解的计算复杂性理论。

范围

近似的复杂性补足了近似算法的研究，后者证明了，针对一些问题，有关问题是否可以有效找到近似解，有一些限制因子。一般来说这些限制会有一个近似因子，若是超过，问题就会变成NP困难，也就是除非NP=P，不然不可能找到多项式时间复杂度的近似解。有些近似复杂性的结果，不过是建立在一些假设上，其中最出名的是唯一游戏假设（英语：unique games conjecture）。

历史

自从1970年代初期，就已知道有些问题只有在P = NP的情形才可能在多项式时间内求解，但许多应用中，可以有效的在一定程度内找到近似最佳的解。在1970年代，Teofilo F. Gonzalez（英语：Teofilo F. Gonzalez）和Sartaj Sahni（英语：Sartaj Sahni）开始研究近似的困难性，证明有些最佳化问题就算是用近似算法近似，此问题也是NP困难。这是因为，这些问题有一个阈值，任何多项式时间的近似，若是近似比例超过此阈值，就可以用此算法在多项式时间内求解NP困难问题^[1]。在1990年代初期，随着PCP（英语：PCP (complexity)）理论的提出，很清楚看出更多的近似问题是很难近似的，除非P = NP，不然很多已知的近似算法已达到最佳的可能近似比例，无法再提升。

近似的困难性理论就是研究这类问题的近似阈值。

例子

像集合覆盖问题就是NP困难的最佳化问题中，也很难有效找到近似解的问题。

相关条目

• PCP定理（英语：PCP theorem）