A Note on polynomial-size monotone proofs of the pigeon hole principle

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/96459

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor.author	Atserias, Albert
dc.date	2000-09
dc.identifier.citation	Atserias, A. "A Note on polynomial-size monotone proofs of the pigeon hole principle". 2000.
dc.identifier.uri	http://hdl.handle.net/2117/96459
dc.language.iso	eng
dc.relation	LSI-00-54-R
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica
dc.subject	Pigeon-hole principle
dc.subject	Polynomial-size monotone proofs
dc.title	A Note on polynomial-size monotone proofs of the pigeon hole principle
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.abstract	We see that the version of the pigeon-hole principle in which every hole is forced to receive a pigeon (called onto) and the version in which every pigeon is mapped into exactly one hole (called functional) have polynomial-size proofs in the tree-like monotone sequent calculus. The proofs are surprisingly simple reductions to the non-monotone case