例如,集合覆盖决策问题被认为是一个NP完全问题。该问题的输入是一个集合U、一个子集族S和一个整数k()。
我感到困惑的一件事是,如果我们让k=1,那么显然问题可以在|S|的时间内解决,只需检查S中的每个元素即可。更一般地,当k是一个常数时,该问题可以在多项式时间内解决。这样,只有当k随着|S|的增加,如|S|/2、|S|/3...时,时间复杂度才会呈指数级增长。
所以我的问题是:
- 我目前的理解是,NP完全问题的时间复杂度测量是以最坏情况下测量的。请问是否正确?
- 我看到有人通过证明一个输入为的集合覆盖决策问题可以归约到另一个问题上来证明该问题是NP难问题。我想知道他为什么只证明,而不是< U,S,任意k >?这样的证明可靠吗?