algorithm - 这是证明某事是 NP Complete 的正确理解吗？

Question

据我所知，有两个步骤可以证明一个问题是 NP 完全的:

1. 给出一个可以在多项式时间内验证问题解的算法。也就是说，一种算法，其输入是问题的建议解决方案，输出是"is"或“否”，具体取决于输入是否是问题的有效解决方案。

2. 证明问题是 NP 难题 - 例如，假设您有一个 oracle 可以一步计算另一个已知的 NP 完全问题。使用它，编写一个在多项式时间内解决此问题的算法。

例如，假设我们要证明下面的问题是NP完全的:

给定一组整数 S，是否可以隔离元素的子集 S'，使得 S 中的元素之和' 是否正好等于 S 中未包含在 S' 中的剩余元素的总和？

第一步:验证算法

Verify_HalfSubset(Set S, Solution sol):
    accum = 0
    for each element i in sol:
        accum+=i
        linear search for an element with the same value as i in S.
        if found, delete it from s, if not found, return false
    end for
    accum2 = 0
    for each element i in S:
        accum2+=i
    end for
    if accum==accum2 return true, else return false

显然这在多项式时间内运行:第一个 for 循环在 O(nm) 内运行，第二个在 O(n) 内运行。

第 2 步:减少

假设我们有一个 oracle O(Set S, int I) 一步计算子集和问题(也就是说，S 中是否有一个元素子集总和为 I )?

然后，我们可以编写一个多项式时间算法来计算我们的半子集问题:

HalfSubset(Set S):
    accum = 0
    for each s in S:
        accum+=S
    end for
    if(accum%2==1) 
    // this question forbids "splitting" values to non-integral parts
        return NO_ANSWER
    end if
    half1 = O(S, accum/2)
    if(half1 == NO_ANSWER)
        return NO_ANSWER
    end if
    for each i in half1:
        linear search for an element with the same value as half1[i] in S
        delete it from S.
    end for
    half2 = S
    return (half1 and half2)

如果我在这个过程中犯了任何错误，有人可以告诉我吗？这是我期末考试复习中的一个问题，我不确定自己是否完全理解。

Answer 1

您的回答的第二部分有点偏离。您在第二步中所说的是，您可以在多项式时间内将此问题简化为已知的 NP 完全问题。也就是说，你是说这个问题至多和 NP 完全问题一样难。

你想说的是NP完全问题可以在多项式时间内简化为你的示例问题。这表明，如果您可以在多项式时间内解决这个问题，那么您也可以在多项式时间内解决 NP 完全问题，证明您的示例问题是 NP 完全问题。