QQ客服 官方微博 反馈留言

	A direct construction of polynomial-size obdd proof of pigeon hole problem
	Chen, Wei1,2; Zhang, Wenhui1
刊名	Information processing letters
	2009-04-30
卷号	109期号:10页码:472-477
关键词	Propositional proof systems Binary decision diagrams Pigeon hole problem Proof complexity Computational complexity
ISSN号	0020-0190
DOI	10.1016/j.ipl.2009.01.006
通讯作者	Chen, wei(cwei@ios.ac.cn)
英文摘要	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 php(n)(n+1) of cutting plane proof system. then it follows directly that there exists polynomial-size proof for php(n)(n+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.
WOS关键词	BINARY DECISION DIAGRAMS
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems
语种	英语
出版者	ELSEVIER SCIENCE BV
WOS记录号	WOS:000265305300004
内容类型	期刊论文
URI标识	http://www.corc.org.cn/handle/1471x/2400757
专题	中国科学院大学
通讯作者	Chen, Wei
作者单位	1.Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China 2.Chinese Acad Sci, Grad Univ, Sch Informat Sci & Engn, Beijing, Peoples R China
推荐引用方式 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.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。