在p、NP、NP-硬和NP-完全中，只有NP完备集被限制于决策问题(那些具有二进制解的问题(。这是什么原因？为什么不把它简单地定义为NP和NP的交集呢？这就引出了另一个问题——一定有一些问题不一定是决策问题，而且还具有NP中的任何问题都可以在多项式时间内归结为决策问题的性质。这是一个包含NP完全的集合吗？这个集合已经有名字了吗？
编辑：根据马特的评论和帖子：NP、NP完全和NP难之间有什么区别？，似乎P和NP只是为决策问题定义的。这将解决这个问题，除了为什么它们会被这样定义之外。但是，这似乎与Cormen等人的《算法导论》一书相矛盾；NP完全性和类P和NP"；，他们只是简单地说："；P由那些在多项式时间内可解的问题组成；。他们后来甚至说；NP完全性并不直接适用于优化问题，而是适用于决策问题；但不要说P和NP。
类p和NP确实是决策问题的类。我手头没有CLRS的副本，但如果他们声称P和NP都是分别在多项式时间或不确定多项式时间内可解的问题，那他们就错了。
将p和NP定义为决策问题集是有帮助的，这有一些很好的理论依据。处理决策问题使可还原性变得更容易(将一个问题简化为另一个问题不需要转换输出(，通过消除问题答案必须有多大的问题来简化模型，使定义不确定性计算更容易，等等。
但这些都不是"交易破坏者"，因为你可以定义涉及计算函数的类似复杂性类，而不仅仅是给出是或否的答案。例如，类FP和FNP是P和NP的函数问题版本，并且FP=FNP的问题同样是开放的。