Partially definable forcing and bounded arithmetic

All of RECERCAT

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

Title:	Partially definable forcing and bounded arithmetic
Author:	Atserias, Albert; Müller, Moritz
Other authors:	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
Abstract:	We describe a method of forcing against weak theories of arithmetic and its applications in propositional proof complexity.
Abstract:	Peer Reviewed
Subject(s):	-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi matemàtica -Computational complexity -Bounded arithmetic -Forcing -Proof complexity -Propositional proof systems -Depth frege proofs -Pigeonhole principle -Complexity gap -Resolution -Size -Complexitat computacional
Rights:
Document type:	Article - Submitted version Article
Share: