NP问题一定是决策问题吗？

Question

斯坦福大学 Tim Roughgarden 教授在教授 慕课 说 NP 类问题的解的长度必须是多项式。但是 维基百科文章 说NP问题是决策问题。那么什么类型的问题基本上属于 NP 类呢？是否有必要说此类问题的解决方案具有多项式长度输出（因为决策问题必然输出 0 或 1）？

Answer 1

事实上，NP 中的问题是对于给定输入字符串输出 0 或 1 的决策问题。Roughgarden 教授指的是这样一个事实：NP 中的问题具有简短的多项式有界证明（在输入长度中），可以有效地验证（通过多项式时间算法）。