NP完全问题的复杂度测量

Question

3

例如，集合覆盖决策问题被认为是一个NP完全问题。该问题的输入是一个集合U、一个子集族S和一个整数k()。

我感到困惑的一件事是，如果我们让k=1，那么显然问题可以在|S|的时间内解决，只需检查S中的每个元素即可。更一般地，当k是一个常数时，该问题可以在多项式时间内解决。这样，只有当k随着|S|的增加，如|S|/2、|S|/3...时，时间复杂度才会呈指数级增长。

所以我的问题是:

我目前的理解是，NP完全问题的时间复杂度测量是以最坏情况下测量的。请问是否正确？
我看到有人通过证明一个输入为的集合覆盖决策问题可以归约到另一个问题上来证明该问题是NP难问题。我想知道他为什么只证明，而不是< U，S，任意k >？这样的证明可靠吗？

非常感谢！

- kostio

要不提供这个人写作的链接，这样我们就不必猜测了？给出一些链接、规范定义集覆盖问题以及解释括号符号的内容会很有帮助。 - David Grayson

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jakub Kotowski · Accepted Answer

时间复杂度是作为输入实例大小的函数来衡量的。输入实例大小可以用比特来衡量。当任何一个输入 U、S 和 k 增加时，输入实例大小也会增加。因此，人们试图回答的问题是解决实例大小为例如 2n 比特的问题需要多长时间，相对于实例大小为 n 的问题。

因此，整个输入实例的大小必须增加，在这种情况下，它意味着增加 U、S 和/或 k 的大小。

回答您的两个问题：

是的，最坏情况时间复杂度被使用：您在寻找输入尺寸为n的最困难问题，并且您正确地注意到与仅有一个参数相比，随着增加更多参数，该问题（相同大小）可能会变得更加困难。
最好看到您所参考的证明，但是思考过程可能如下：

我提供了一个规模为n的集合覆盖决策问题实例到我的问题实例的多项式规约。如果集合覆盖决策问题的输入实例的大小增加到2n，则规约的结果将是我问题实例的大小2m，因为输入大小的U，S和k与我的问题的输入大小之间存在直接对应关系。

因此，所有大小为n的集合覆盖决策问题实例都映射到我的问题实例的大小m。因此，如果我使用此规约寻找集合覆盖决策问题的最困难实例，则将找到我的问题大小为m的最困难实例。

编辑

根据您提供的文章中的证明：

证明。我们将任意一个3-覆盖问题实例（其中我们给定一个宇宙U，一个包含U的子集族S，每个子集包含3个元素，并且我们被要求使用S的|U|/3个元素来（恰好）覆盖所有U），转化为一个具有同构资源和大小为3的调度的游戏。

正如您所说，他们需要将集合覆盖问题的所有实例转换为他们的问题。但是，他们在使用不同问题的约简：精确的3-覆盖问题，在1979年的“计算机与难题”（MR Garey，DS Johnson）中已被证明是NP完全问题。

精确的3-覆盖问题类似于集合覆盖决策问题，但满足|U| = 3t和S是U的一组由3个元素组成的子集。