我有一个调度问题需要解决。我需要证明该问题是NP完全问题。有什么方法可以证明它是NP完全问题吗?
我有一个调度问题需要解决。我需要证明该问题是NP完全问题。有什么方法可以证明它是NP完全问题吗?
C
,您可以创建一个多项式时间的算法V
,该算法将为每个可能的输入X
验证X
是否在您的域中。
G
,是否存在一个大小为k
的顶点覆盖集,使得G
中的每条边都至少有一个顶点在覆盖集中?)属于NP:
我们的输入X
是一些图G
和一些数字k
(这是从问题定义中得出的)。
取C
为“图G
中大小为k
的任何可能的顶点子集”。
然后,我们可以编写一个算法V
,在给定G
、k
和C
的情况下,在多项式时间内返回该顶点集是否为G
的顶点覆盖。
G
,如果存在某个“可能的大小为k
的G
中的顶点子集”是一个顶点覆盖,则G
属于NP
。
注意,我们不需要在多项式时间内找到C
。如果我们可以这样做,该问题将属于。
注意算法V
应该针对每一个G
,对于某些C
都能工作。对于每个输入,应该存在信息可以帮助我们验证输入是否在问题域内,也就是说,不应该存在信息不存在的输入。
这涉及到获取一个已知的NP完全问题,比如SAT,其中包括形式为:
(A或B或C)和(D或E或F)等布尔表达式的集合……
其中表达式是可满足的,也就是说存在一些布尔值的设置,使得表达式成为真。
然后将NP完全问题在多项式时间内约化到你的问题上。
也就是说,给定一些输入X
用于SAT
(或者你正在使用的任何NP完全问题),创建一些输入Y
用于你的问题,使得当且仅当X
在SAT中时,Y
在你的问题中。函数f:X→Y
必须在多项式时间内运行。
在上面的例子中,输入Y
将是图形G
和顶点覆盖的大小k
。
对于一个完整的证明,你需要证明以下两点:
X
在SAT
中=>Y
在你的问题中
Y
在你的问题中=>X
在SAT
中。
marcog的答案中包含了一个链接,链接中提到了其他几个可以通过约化转化为你所面临问题的NP完全问题。
脚注:在第二步(证明它是NP难问题)中,只要将另一个NP难问题(不一定是NP完全问题)约化到当前问题上就可以了,因为NP完全问题是NP难问题的子集(且也属于NP)。
首先,您需要证明该问题至少属于NP。
然后,您需要找到另一个已知为NP完全的问题,并展示如何将NP难问题多项式归约为您的问题。