抽象問題

抽象問題為在問題實例集合和問題答案集合上的一個關係。

定義

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

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

性質

現定義 編碼如下：

抽象問題

抽象問題

抽象問題

抽象對象集合

的編碼是從到二進制串集合的映射。

抽象問題

抽象問題

抽象問題

抽象問題

求解某個抽象判定問題的計算機算法實質上是把一個問題實例的編碼作為其輸入。我們把實例集為二進制串的集合的問題稱為具體問題。當提供給一個算法的長度是的一個問題實例時，算法可以在時間內產生問題的解，我們就稱該算法在內解決了該具體問題。

套用

抽象問題

抽象問題

抽象問題

抽象問題

抽象問題

抽象問題

抽象問題

抽象問題

抽象問題

設是定義在一個實例集上的一個抽象判定問題，和是上多項式相關的編碼，則若且唯若。其中表示對應的具體問題是一個多項式時間問題。