使用NP缩减

Question

我一直有一些困难，理解减少使用NP问题，并希望澄清。考虑以下问题：

Show that the following problem is NP-Complete by designing
a polynomial-time reduction algorithm from an already known
NP-Complete problem.

Problem: Given an undirected graph G=(V,E) and integer k,
         test whether G has a cycle of length k.

我知道还有关于这个问题的其他议题，但我仍然不确定我是否理解这样的削减将如何进行。

我的理解是，这就是你处理这样一个问题的方法。

1. 假设给定的问题可以在多项式时间内求解。
2. 用给定的问题来解决我们知道的在多项式时间是NP-Hard的问题。
3. 这造成了一个矛盾，所以这个假设肯定是不正确的。
4. 因此，给定的问题在多项式时间内是不可解的。

那么，对于这样的问题，这是一个正确的方法吗？

1. 如果我们选择k作为图中哈密顿圈的长度(假设有一个)，这就意味着这个问题可以用来求图中的哈密顿圈。
2. 由于我们只能在NP时间中找到哈密顿循环，所以这个问题也只能在NP时间中才能解。

Answer 1

这看起来很像家庭作业，所以我只给您一个提示，但是尝试考虑一个带有k节点的未加权图k。什么是等价于寻找一个周期的长度k，这是可解的算法，你假设的是多项式？试着从这里开始。