用语言表达是与否
判定问题是对输入作肯定或否定回答的计算问题类型，不专指历史上希尔伯特提出的逻辑判定问题。其对象通常是一整类可能输入，例如所有有限图及指定顶点，而不是某一个已经知道答案的孤立事实。算法必须用同一套有限规则处理这些输入。
为形式化问题，可把图、整数、公式等对象编码为有限字母表上的字符串。所有答案为“是”的编码组成语言L，任务就成为判断给定字符串x是否属于L。这样的表达使外观不同的问题可以在同一个模型下讨论可计算性、归约以及时间和空间复杂度。
同一对象上的不同任务
给定有向图G和顶点s、t，询问“是否有从s到t的路径”是判定问题；要求输出一条这样的路径，是搜索问题；要求输出最短路径的长度，是优化问题；要求计算简单路径的条数，则是计数问题。它们使用相似输入，却有不同的输出要求。
搜索成功时，给出的对象往往能证明判定答案为是，但判定程序输出的一个比特并没有直接提供那个对象。有些问题可用多次判定查询逐步恢复解，有些则需要额外结构和证明。不能仅因题目都涉及路径，就默认所有版本在任何资源限制下完全等价。
编码和输入范围不能省略
复杂度通常按编码长度计算，而不是按输入对象的数值大小计算。整数用二进制表示时，长度随其对数增长；用一元记号表示时，长度随数值增长。同一个看似关于整数的过程，换了这种编码后，关于输入长度的运行时间分类可能改变。合理的二进制与十进制编码则可高效互换。
还要约定哪些字符串是合法编码，以及非法编码如何处理。若问题预先保证输入属于某个受限集合，例如只给连通图，这项承诺也应明说。承诺外输入不要求按原问题作答，与把它们统一定义为否实例，是不同的问题规定，不能在证明途中悄悄切换。
有答案不等于有判定算法
一个判定算法必须对范围内每个输入停机，并给出正确答案。只在肯定实例上保证最终接受，而在某些否定实例上可能不停机的过程，是识别器，不足以成为判定器。“再等一会儿也许有结果”不能作为否定答案的通用判据。
因此，问题有明确的真假条件，与存在统一算法，是两层不同要求。确认可判定之后，仍可继续问它能否在多项式时间或很少空间内解决；相反，某个程序在一个实例上算出结果，也不能单独证明它对无限多种输入都正确且会终止。判定问题的价值，正在于把这些要求分开，形成可精确检验的理论对象。