以文本方式查看主题 - 中文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 是否有效。 请高人说明一下(证明思路)或者文献出处。 |
-- 作者:yswang168 -- 发布时间:1/6/2014 8:19:00 PM -- \Pi_2 3-SAT的复杂性是\Pi_2^P-完全的。 思路是:1)\forall X \exists Y SAT是 \Pi_2^P完全的 故得。参考: 如不对,请高人指点。 |
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
31.982ms |