显示NP的Decison版本

2018-06-14 01:06:02

假设你有一个组合优化问题A.让我们假设WLOG问题是团体问题。

我怎么能证明，如果集团是NP完全的，那么集团的决定版本是NP完全的，其中决定版本当然是以下问题B：是否有一个大小等于k的集合？

我想我有直觉，但不知道它是否足以作为证明：

第一步：

如果给定一组k的顶点C，我可以在多项式时间验证存在一个k大小的集合（假设对B的答案是肯定的，即存在大小为k的集合）。因此，B在NP中。

第二步：将A减少到B.

- 因为A要求最大尺寸的团体，所以我们可以把问题分解成几部分，B1：是否有一个大小为1的团体？，...，BN：是否有一个大小为N的团体？

如果A是可解的，说有一个大小为k *的集合，那么每个Bk，k = 1，...，N都可以通过比较k和k *

- 如果所有的BKS都可以解决，我们可以告诉最大的团体规模是多少。

我真的不确定这是多少时间的减少。也许是因为一个问题被分解成许多问题。此外，我不确定我应该使用上面的“全部”这个词。

谢谢您的帮助！ :)

组合优化问题不能是NP完全的。只有决策问题可以是NP完全的（参见，例如http://en.wikipedia.org/wiki/NP-complete）。

因为它的决策版本（给定一个图和ak，是否有一个大小大于等于k的集合）是NP-hard问题，所以Clique优化问题（给定一个图，找到一个形成团的最大顶点集）完成。

链接地址: http://www.djcxy.com/p/39997.html

下一篇: How is TSP NP