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

Title:	A Note on polynomial-size monotone proofs of the pigeon hole principle
Author:	Atserias, Albert
Other authors:	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
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
Subject(s):	-Àrees temàtiques de la UPC::Informàtica -Pigeon-hole principle -Polynomial-size monotone proofs
Rights:
Document type:	Article - Published version Report
Share: