A direct construction of polynomial-size OBDD proof of pigeon hole problem
type: Item
instance of: scholarly article
title: A direct construction of polynomial-size OBDD proof of pigeon hole problem
zbMATH Open document ID: 1217.03044
published in: Information Processing Letters
publication date: 2010-08-16T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5771243
zbMATH Keywords: propositional proof systems
zbMATH Keywords: binary decision diagrams
zbMATH Keywords: pigeonhole problem
zbMATH Keywords: proof complexity
zbMATH Keywords: computational complexity
author: Wei Chen
author: Wenhui Zhang
describes a project that uses: CUDD
MaRDI profile type: Publication
full work available at URL: j.ipl.2009.01.006
OpenAlex ID: W2035447984
cites work: Principles and Practice of Constraint Programming – CP 2004
cites work: Graph-Based Algorithms for Boolean Function Manipulation
cites work: The relative efficiency of propositional proof systems
cites work: On the complexity of cutting-plane proofs
cites work: Resolution and binary decision diagrams cannot simulate each other polynomially
cites work: An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams
cites work: Symbolic techniques in satisfiability solving
cites work: Branching Programs and Binary Decision Diagrams
DOI: 10.1016/J.IPL.2009.01.006
description: scientific article; zbMATH DE number 5771243