抽象问题为在问题实例集合和问题答案集合上的一个关系。

以上为抽象问题的形式化定义。

例如：SHORTEST-PATH的一个实例是由一个图和两个顶点所组成的三元组，其届问图中的顶点序列，序列可能为空，表示两点间不存在通路。问题SHORTEST-PATH本身就是一个关系，它把图的每个实例和两个顶点组成的三元组与图中两个顶点间的最短路径联系起来。最短路径不一定是唯一的，故一个给定的问题实例可能有多个解。

现定义编码如下：

抽象对象集合的编码是从到二进制串集合的映射。

求解某个抽象判定问题的计算机算法实质上是把一个问题实例的编码作为其输入。我们把实例集为二进制串的集合的问题称为具体问题。当提供给一个算法的长度是的一个问题实例时，算法可以在时间内产生问题的解，我们就称该算法在内解决了该具体问题。

设是定义在一个实例集上的一个抽象判定问题，和是上多项式相关的编码，则当且仅当。其中表示对应的具体问题是一个多项式时间问题。