近似的困難性

計算機科學中，近似的複雜性（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）