NP的复杂度测量
例如，集合覆盖决策问题被认为是一个NP完全问题。 这个问题的输入是宇宙U，U的子集S和一个整数k（）。
我混淆的一件事是，如果我们让k = 1，那么通过简单地检查S中的每个元素，显然问题可以在时间| S |中解决。更一般地，当k是常数时，问题可以在| S |的多项式时间内求解。 以这种方式，只有当k也随着| S |增加时，如| S | / 2，| S | / 3 ...，时间复杂度才会呈指数级增长。
所以这里是我的问题：
我目前的理解是，NP完全问题的时间复杂度测量是根据最差情况来衡量的。 任何人都可以告诉我，如果理解是正确的？
我看到有人通过证明输入<U,S,|U|/3>的集合覆盖问题可以简化为这个问题，证明另一个问题是NP难题。 我只是想知道他为什么只证明<U,S,|U|/3> ，而不是<U,S,ARBITRARY k> ？ 这样的证明是否可靠？
非常感谢！
时间复杂度是根据输入实例大小来测量的。 输入实例的大小可以用位来衡量。 输入实例大小随着输入U ， S和k任何一个增加而增加。 因此，人们试图回答的问题是需要多少时间来解决实例大小问题，例如2n位与实例大小n的问题。
因此，简单地说整个输入实例的大小必须增加，在这种特殊情况下，它意味着增加U和/或S和/或k 。
回答你的两个问题：
n最难的问题，并且您正确地注意到（相同大小的）问题可能变得更难，因为您增加的参数不止一个。 最好能看到你提到的证据，但这个想法可能是这样的：
我给出了大小为n的集覆盖决策问题实例的多项式约化到我的问题的大小为m的实例。 如果集合覆盖决策问题的输入实例的大小增加到2n那么减少的结果将是我的问题的大小为2m的实例，因为U ， S和k的输入大小与输入大小之间存在直接对应关系我的问题。
因此，所有大小为n集合覆盖决策问题实例映射到大小为m问题实例。 因此，如果我正在寻找使用这种减少的集合覆盖决策问题的最困难的例子，我会发现我的规模为m问题的最困难的例子。
编辑
从你的链接文件中的证明：
证明。 我们减少一个任意的3覆盖问题实例 - 在这个实例中我们得到一个宇宙U，U的子集S，使得每个子集包含3个元素，并且我们被问到是否可以（确切地）覆盖所有U | U | / 3个元素的S - 到一个具有同等资源和大小为3的时间表的游戏。
正如你所说的，他们需要将所有机顶盒问题转换为他们的问题。 但他们正在从一个不同的问题中减少：在“计算机和难处理 - MR Garey，DS Johnson，1979”中被证明是NP完全的精确3覆盖问题。
精确3覆盖问题与集合覆盖决策问题相似，但是|U| = 3t |U| = 3t ， S是U一个3元素子集。