3

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

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

所以这是我的问题：

  1. 我目前的理解是，NP完全问题的时间复杂度测量是根据最坏情况来测量的。谁能告诉我理解是否正确？

  2. 我看到有人证明了另一个问题是 NP 难的，他证明输入的集合覆盖决策问题<U,S,|U|/3>可以简化为该问题。我只是想知道为什么他只证明了<U,S,|U|/3>，而不是<U,S,ARBITRARY k>？？这样的证明可靠吗？

非常感谢！

4

1 回答 1

1

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

所以简单地说，整个输入实例的大小必须增加，在这种特殊情况下，这意味着增加U和/或S和/或的大小k。

回答你的两个问题：

  1. 是的，使用了最坏情况的时间复杂度：您正在寻找最难的输入大小问题，n并且您正确地注意到，当您增加更多参数而不仅仅是一个参数时，问题（相同大小）可能会变得更难。

  2. 最好看看你所指的证明，但想法可能是这样的：

    我将集合覆盖决策问题实例 size 的多项式归约n到我的问题实例 size m。如果集合覆盖决策问题的输入实例的大小增加到 ，2n那么缩减的结果将是我的问题的大小实例，因为、和的输入大小与我的问题的输入2m大小之间存在直接对应关系。USk

    因此，所有大小的集合覆盖决策问题实例都n映射到我的大小问题实例m。因此，如果我正在寻找使用这种缩减的集合覆盖决策问题的最难实例，我将找到我的 size 问题的最难实例m。

编辑

从您链接的论文中的证明：

证明。我们减少了一个任意的 3-cover 问题实例——给定一个全域 U，一个 U 子集的族 S，每个子集包含 3 个元素，并且我们被问到我们是否可以（准确地）覆盖所有 U 使用|U|/S 的 3 个元素——具有同质资源和大小为 3 的时间表的博弈。

正如您所说的那样，他们需要将集合覆盖问题的所有实例转换为他们的问题。但是他们使用了一个不同问题的归约方法：Exact 3-cover 问题，该问题在“Computers and intractability - MR Garey, DS Johnson, 1979”中被证明是 NP 完全的。

Exact 3-Cover 问题类似于集合覆盖决策问题，但具有|U| = 3t和S是 的 3 元素子集U。

于 2014-01-06T08:57:25.183 回答