所有已知的解決NP-難問題演算法都有指數型執行時間。但是，如果我們要找一個“好”解而非最優解，有時候多項式演算法是存在的。

給定一個最小化問題和一個近似演算法，我們按照如下方法評價演算法：首先給出最優解的一個下界，然後把演算法的執行結果與這個下界

進行比較。對於最大化問題，先給出一個上界然後把演算法的執行結果與這個上界比較。

近似演算法比較經典的問題包括：最小頂點覆蓋、旅行售貨員問題、集合覆蓋等。

迄今為止，所有的NP完全問題都還沒有多項式時間演算法。

對於這類問題，通常可採取以下幾種解題策略。

(1)只對問題的特殊例項求解

(2)用動態規劃法或分支限界法求解

(3)用機率演算法求解

(4)只求近似解

(5)用啟發式方法求解

若一個最最佳化問題的最優值為c*，求解該問題的一個近似演算法求得的近似最優解相應的目標函式值為c，

則將該近似演算法的效能比定義為max(c/c*, c*/c)。在通常情況下，該效能比是問題輸入規模n的一個函式

ρ(n)，即 max(c/c*, c*/c)

該近似演算法的相對誤差定義為Abs[(c-c*)/c*]。若對問題的輸入規模n，有一函式ε(n)使得Abs[(c-c*)/c*]

關係：ε(n)≤ρ(n)-1。