电路可满足性问题是NPC问题

电路可满足性问题是NPC问题
【电路可满足性问题】
电路可满足性问题(Circuit satisfiability problem)描述为:给定一个电路,需要确定是否存在对输入的赋值使得输出值为1。如果存在这样的赋值,则称这个电路是可满足的。这个赋值也被称为一个满足的赋值。如图5为电路可满足性问题的一个实例。
在这里插入图片描述
图5 电路可满足性问题
图中的左边,从上到下依次是或门、非门。图中的右边是与门。当1和2输入都为1,3输入为0的时候,输出为1。即这个电路是满足的。

定理6.电路可满足性问题是NPC问题。
电路可满足性问题是NPC。这个定理是Cook和Levin于1971年提出的。
证明电路可满足性问题是NPC的,根据NPC定义,需要证明以下两点:
(1)电路可满足性问题是NP问题。
(2)所有的NP问题都可以归约到电路可满足性问题。
证明:
(1)对于电路的每一个输入,只需要验证其结果是否是1即可。因此能够在多项式时间内验证答案是否正确。即电路可满足性问题是NP问题。
(2)对于一个问题,可以将输入的实例s和证书t,构造一个输入长度为(|s|+|t|)的电路。即有(|s|+|t|)个源结点(输入结点)。很容易看到,一定有办法设计电路,使得电路的输出为1。即电路是可满足的。表明所有的NP问题都可以归约为电路可满足性问题。
因此,电路可满足性问题是NPC问题。

0

Leave a Reply

Your email address will not be published.