抽象問題

以上為抽象問題的形式化定義。

例如：SHORTEST-PATH的一個實例是由一個圖和兩個頂點所組成的三元組，其屆問圖中的頂點序列，序列可能為空，表示兩點間不存在通路。問題SHORTEST-PATH本身就是一個關係，它把圖的每個實例和兩個頂點組成的三元組與圖中兩個頂點間的最短路徑聯繫起來。最短路徑不一定是唯一的，故一個給定的問題實例可能有多個解。

現定義編碼如下：

抽象對象集合

的編碼是從

到二進制串集合的映射

。

求解某個抽象判定問題的計算機算法實質上是把一個問題實例的編碼作為其輸入。我們把實例集為二進制串的集合的問題稱為具體問題。當提供給一個算法的長度是

的一個問題實例

時，算法可以在

時間內產生問題的解，我們就稱該算法在

內解決了該具體問題。

設

是定義在一個實例集

上的一個抽象判定問題，

和

是

上多項式相關的編碼，則

當且僅當

。其中

表示

對應的具體問題是一個多項式時間問題。