问基于NP验证的定义
EN

Stack Overflow用户

提问于 2011-07-05 02:11:00

回答 2查看 1.5K关注 0票数 0

我是一名计算机科学专业的学生，我在理解基于验证器的NP问题定义时遇到了一些问题。

这个定义说，如果一个问题可以在多项式时间内被确定性的图灵机验证，那么这个问题就是NP中的问题。

但是，如果证书正是问题的解决方案，会发生什么呢？它只是一小部分，而且它明显受到输入大小的多项式限制，而且它显然是可以在常数中验证的，因此多项式时间。

因此，每个决策问题都属于NP。

我哪里错了？

发布于 2011-07-05 02:17:14

即使解的长度是多项式的，也不是所有的问题都能在多项式时间内得到验证。让我们考虑旅行推销员问题。给定一个解决方案，您只能验证给定的解决方案是否是城市之旅，但您无法判断它是否是最小长度的游览，除非您探索所有可能的游览。

因此，在大多数情况下，决策问题是NP完全的(例如，查找城市集合是否包含旅游)，而优化问题是NP难的(例如，找到最小长度的旅游)。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/6574796

复制

相似问题

问基于NP验证的定义EN