据我了解,有两个步骤可以证明问题是 NP 完全的:
给出一个算法,它可以在多项式时间内验证问题的解决方案。也就是说,一种算法,其输入是对问题提出的解决方案,其输出是“是”或“否”,这取决于输入是否是问题的有效解决方案。
证明问题是 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)
如果我在这个过程中犯了任何错误,有人可以告诉我吗?这是我期末考试复习中的一个问题,我不确定我是否完全理解。