2

据我了解,有两个步骤可以证明问题是 NP 完全的:

  1. 给出一个算法,它可以在多项式时间内验证问题的解决方案。也就是说,一种算法,其输入是对问题提出的解决方案,其输出是“是”或“否”,这取决于输入是否是问题的有效解决方案。

  2. 证明问题是 NP 难题 - 例如,假设您有一个预言机可以一步计算另一个已知的 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 步:减少

假设我们有一个预言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)

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

4

2 回答 2

3

不,这是不正确的。您可以设置一种情况,使用 NP-Complete oracle 来解决问题,但问题本身仍然存在于 P 中。

你要做的是证明你可以将另一个 NP-Complete 问题简化为你的问题。也就是说,提供一个多项式时间算法来将特定 NP-Complete 问题的任何实例转换为您的问题的一个实例,这样您的(转换后的)问题的解决方案也是给定 NP-Complete 问题的解决方案。这表明如果你能解决你的问题,那么你也可以解决任何 NP-Complete 问题,这意味着你的问题至少与任何其他 NP-Complete 问题一样难。

于 2013-12-12T18:00:05.270 回答
3

你答案的第二部分有点不对劲。您在第二步中所说的是,您可以在多项式时间内将此问题简化为已知的 NP 完全问题。也就是说,您是说这个问题最多与 NP 完全问题一样难。

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

于 2013-12-12T18:02:02.697 回答