抽象問題

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

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

現定義 編碼如下：

抽象對象集合的編碼是從到二進位串集合的映射。

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

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