, 取值为真即可 ;
验证过程所花的时间与联结词个数有关 , 联结词的个数 , 肯定布会超过布尔逻辑公式的长度 ,
验证所花费的时间一定是 多项式时间 ,
因此 布尔可满足性问题 在
\rm NP...接受 字符串
\rm w
, 当且仅当 构造出的逻辑公式是可满足的 ;
构造该逻辑公式 :
构造如下表格 , 将整个 非确定性图灵机
\rm N
在字符串上作一个计算 , 计算的分支 , 通过一个表格装进去...\rm j
的格子 Cell ) 对应的字符是
\rm s
;
得到布尔逻辑公式 : 上述表格中的格子中 , 任何格子 , 只包含一个字符 , 并且只能包含一个字符 , 该公式的长度是多项式长度...开始格局 , 在所有的表格中 , 一定包含了一个接受格局 , 其中一定包含了有一个状态 , 是接受状态 ;
\rm \phi_{start} = x_{1,1,\#} \land x_{1,2,q_0...rm \phi
的长度是 多项式长度 ,
可以将
\rm NP
中的任何计算问题 在 多项式时间中规约到
\rm SAT
问题 ( 布尔可满足性问题 ) , 布尔可满足性问题 是
\rm P