我是一名计算机科学专业的学生，我在理解基于验证器的 NP 问题定义时遇到了一些问题。
该定义说，如果可以在给定“证书”的情况下通过确定性图灵机在多项式时间内验证问题，则该问题存在于 NP 中。
但是，如果证书正是问题的解决方案，会发生什么？它只是一点点，它显然受到输入大小的多项式限制，并且显然可以在常数中验证，因此是多项式时间。
因此，每个决策问题都属于 NP。
我哪里错了？
问问题
1613 次
2 回答
1
但是，如果证书正是问题的解决方案，会发生什么？它只是一点点，它显然受到输入大小的多项式限制，并且显然可以在常数中验证，因此是多项式时间。
为什么是“显然”？您可能需要花费指数级的时间来验证解决方案，在这种情况下，问题不必出现在 NP 中。关键是，即使证书是决策问题的单个位，您也不知道该位应该是零还是一来解决问题。（如果你总是知道这一点，那么 P 或 NP 中的任何决策问题都可以在恒定时间内解决。）
于 2011-07-04T18:15:24.847 回答
0
即使解决方案的长度是多项式，也不是所有问题都可以在多项式时间内得到验证。让我们考虑旅行商问题。给定一个解决方案，您只能验证给定的解决方案是否是城市游览，但您无法判断它是否是最短长度游览，除非您探索所有可能的游览。
因此，在大多数情况下，决策问题是 NP-Complete（例如，查找城市集是否包含旅游），而优化问题是 NP-Hard（例如，查找最小长度的旅游）
于 2011-07-04T18:17:14.373 回答