以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 理论计算机科学 』  (http://bbs.xml.org.cn/list.asp?boardid=64)
----  \Pi_2 3-SAT的复杂性是\Pi_2^P-完全的吗[求助]  (http://bbs.xml.org.cn/dispbbs.asp?boardid=64&rootid=&id=128040)


--  作者:yswang168
--  发布时间:1/6/2014 11:48:00 AM

--  \Pi_2 3-SAT的复杂性是\Pi_2^P-完全的吗[求助]
[color=#0000FF][size=2]请教一个复杂性问题:
\Sigma_2 3-SAT是\Sigma_2^P-完全的,也看到有人说\Pi_2 3-SAT的复杂性是\Pi_2^P-完全的。 我想确认一下。

\Sigma_2 3-SAT是:\exists X \forall Y 3-CNF 是否有效。
\Pi_2 3-SAT是:\forall X \exists  Y 3-CNF 是否有效。

请高人说明一下(证明思路)或者文献出处。
[/size][/size][/color]


--  作者:yswang168
--  发布时间:1/6/2014 8:19:00 PM

--  
\Pi_2 3-SAT的复杂性是\Pi_2^P-完全的。

思路是:1)\forall X \exists Y SAT是 \Pi_2^P完全的
          ==〉\forall x \exists Y\exits Z CNF*是\Pi_2^P完全的(CNF*是由SAT经过引入新变元Z线性变换成CNF形式,保持可满足性等价)
         ==〉\forall x \exists Y\exits Z \exists Z' 3-CNF*是\Pi_2^P完全的(CNF*是由SAT经过引入新变元Z线性变换成3-CNF形式,保持可满足性等价)

故得。参考:
Handbook of complexity:
Chapter 23 Theory of Quantified Boolean Formulas
Hans Kleine B¨uning and Uwe Bubeck

如不对,请高人指点。


W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
31.982ms