a direct construction of polynomial-size obdd proof of pigeon hole problem
文献类型：期刊论文
| 作者 | Chen Wei ; Zhang Wenhui |
| 刊名 | INFORMATION PROCESSING LETTERS
 |
| 出版日期 | 2009 |
| 卷号 | 109期号:10页码:472-477 |
| 关键词 | Propositional proof systems Binary decision diagrams Pigeon hole problem Proof complexity Computational complexity |
| ISSN号 | 0020-0190 |
| 学科主题 | Computer Science ; Information Systems |
| 公开日期 | 2011-03-18 |
| 附注 | Viewing OBDD from the explicit perspective of a propositional proof system is first proposed and studied in A. Atserias, P.G. Kolaitis, M.Y. Vardi, Constraint propagation as a proof system, in: CP, 2004, pp. 77-91. It has been shown that OBDD proof system defined in A. Atserias, P.G. Kolaitis, M.Y. Vardi, Constraint propagation as a proof system, in: CP, 2004, pp. 77-91 is strictly stronger than resolution and can polynomially simulate cutting plane proof system with small coefficients CP*. It is already shown in (W. Cook, C.R. Coullard, G. Turan, On the complexity of cutting-plane proofs, Discrete Appl. Math. 18 (11) (1987) 25-38 that there exists polynomial-size proof for pigeon hole problem PHPnn+1 of cutting plane proof system. Then it follows directly that there exists polynomial-size proof for PHPnn+1 of OBDD proof system. However, this is an indirect result. Atserias et al. A. Atserias, P.G. Kolaitis, M.Y. Vardi, Constraint propagation as a proof system, in: CP, 2004, pp. 77-91 call for the need of a direct construction. Hereby we present such construction. Moreover, in this construction we do not need the weakening rule introduced in A. Atserias, P.G. Kolaitis, M.Y. Vardi, Constraint propagation as a proof system, in: CR 2004, pp. 77-91. We believe this may shed some light on the understanding of the role of the weakening rule. (C) 2009 Elsevier B.V. All rights reserved. |
| 源URL | [http://124.16.136.157/handle/311060/8032]  |
| 专题 | 软件研究所_计算机科学国家重点实验室 _期刊论文 |
| 推荐引用方式 GB/T 7714 | Chen Wei,Zhang Wenhui. a direct construction of polynomial-size obdd proof of pigeon hole problem[J]. INFORMATION PROCESSING LETTERS,2009,109(10):472-477. |
| APA | Chen Wei,&Zhang Wenhui.(2009).a direct construction of polynomial-size obdd proof of pigeon hole problem.INFORMATION PROCESSING LETTERS,109(10),472-477. |
| MLA | Chen Wei,et al."a direct construction of polynomial-size obdd proof of pigeon hole problem".INFORMATION PROCESSING LETTERS 109.10(2009):472-477. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。