最小顶点覆盖的验证算法？

Question

我们知道最小顶点覆盖是NP完全问题，这意味着它属于可以在多项式时间内验证的问题集合。

据我理解，验证过程需要以下步骤：

1. 验证解决方案是否真的是一个顶点覆盖。 2. 验证解决方案是满足条件1的源图中最小可能的子集。

我发现很难建立第二个步骤可以在多项式时间内完成。有人能解释一下吗？

- Govind Parmar

Answer 1

最小顶点覆盖问题是NP难的。仅当其作为决策问题，并且可以在多项式时间内验证时，才是NP完全的。

最小顶点覆盖问题是在给定图中找到最小顶点覆盖的优化问题。

• 输入：图G
• 输出：最小数k，使得G具有大小为k的顶点覆盖。

如果将问题陈述为决策问题，则称为顶点覆盖问题：

• 输入：图G和正整数k
• 问题：是否存在大小不超过k的顶点覆盖？

将问题重新陈述为决策问题是使问题成为NP完全问题的常见方法。基本上，您将“寻找最小解k”这种开放式问题转化为一个是/否问题，“对于给定的k，是否存在解？”

例如，对于旅行商问题，验证一个被提出的解决方案是否为连接所有城市的最短路径是NP难问题。但如果问题重新表述为只需要找到一条总距离小于k的解决方案，则验证解决方案就很容易了。你只需找到所提出解决方案的长度并检查它是否小于k。

决策问题的表述可以轻松地用于解决一般的表述。要找到最短路径，您只需要逐步降低k的值，直到找不到解决方案为止。

- John Kugelman

---

但是，如果某件事情很容易，并不意味着它解决起来也很快吧？没有问题需要很长时间，这就是问题所在。 - Micromega

@Phpdna 在寻找解决方案和验证解决方案之间有一个关键的区别，前者是NP问题，后者是P问题。 NP完全问题是指可以“轻松”验证解决方案（在多项式时间内）。我不知道如何找到在500英里内经过五个城市的路线，但如果有人给我一个解决方案，我可以很容易地检查他们的路线是否比500英里更短。 - John Kugelman

仍然没有提到解决方案。关于找到某个（决策）问题，这真的很难理解吗？毕竟它甚至不是真正的科学？ - Micromega