近似的困难性

计算机科学中，近似的複雜性（hardness of approximation）是研究最佳化問題中，有關尋找接近最佳解的計算複雜性理論。
範圍
近似的複雜性補足了近似算法的研究，後者證明了，針對一些問題，有關問題是否可以有效找到近似解，有一些限制因子。一般來說這些限制會有一個近似因子，若是超過，問題就會變成NP困难，也就是除非NP=P，不然不可能找到多項式时间复杂度的近似解。有些近似複雜性的結果，不過是建立在一些假設上，其中最出名的是。

歷史
自從1970年代初期，就已知道有些問題只有在P = NP的情形才可能在多項式時間內求解，但許多應用中，可以有效的在一定程度內找到近似最佳的解。在1970年代，和開始研究近似的困難性，證明有些最佳化問題就算是用近似算法近似，此問題也是NP困難。這是因為，這些問題有一個閾值，任何多項式時間的近似，若是近似比例超過此閾值，就可以用此算法在多項式時間內求解NP困難問題.。在1990年代初期，隨著理論的提出，很清楚看出更多的近似問題是很難近似的，除非P = NP，不然很多已知的近似演算法已達到最佳的可能近似比例，無法再提昇。

近似的困难性理論就是研究這類問題的近似閾值。

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

相關條目


參考資料

延伸閱讀

外部連結
 CSE 533: The PCP Theorem and Hardness of Approximation, Autumn 2005, syllabus from the University of Washington, Venkatesan Guruswami and Ryan O'Donnell

Category:近似演算法
Category:計算複雜性理論