近似的困难性
计算机科学中，近似的複雜性（hardness of approximation）是研究最佳化問題中，有關尋找接近最佳解的計算複雜性理論。
範圍
[编辑]近似的複雜性補足了近似算法的研究，後者證明了，針對一些問題，有關問題是否可以有效找到近似解，有一些限制因子。一般來說這些限制會有一個近似因子，若是超過，問題就會變成NP困难，也就是除非NP=P，不然不可能找到多項式时间复杂度的近似解。有些近似複雜性的結果，不過是建立在一些假設上，其中最出名的是唯一遊戲假設。
歷史
[编辑]自從1970年代初期，就已知道有些問題只有在P = NP的情形才可能在多項式時間內求解，但許多應用中，可以有效的在一定程度內找到近似最佳的解。在1970年代，Teofilo F. Gonzalez和Sartaj Sahni開始研究近似的困難性，證明有些最佳化問題就算是用近似算法近似，此問題也是NP困難。這是因為，這些問題有一個閾值，任何多項式時間的近似，若是近似比例超過此閾值，就可以用此算法在多項式時間內求解NP困難問題[1]。在1990年代初期，隨著PCP理論的提出，很清楚看出更多的近似問題是很難近似的，除非P = NP，不然很多已知的近似演算法已達到最佳的可能近似比例，無法再提昇。
近似的困难性理論就是研究這類問題的近似閾值。
例子
[编辑]像集合覆盖问题就是NP困難的最佳化問題中，也很難有效找到近似解的問題。
相關條目
[编辑]參考資料
[编辑]- ^ Sahni, Sartaj; Gonzalez, Teofilo, P-complete approximation problems, Journal of the ACM, 1976, 23 (3): 555–565, MR 0408313, doi:10.1145/321958.321975, hdl:10338.dmlcz/103883
.
延伸閱讀
[编辑]- Trevisan, Luca, Inapproximability of Combinatorial Optimization Problems (PDF), July 27, 2004, Bibcode:2004cs........9043T, arXiv:cs/0409043
外部連結
[编辑]- CSE 533: The PCP Theorem and Hardness of Approximation, Autumn 2005, syllabus from the University of Washington, Venkatesan Guruswami and Ryan O'Donnell