以文本方式查看主题

-  中文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号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 4,716.797ms