Comments on Beckmann's Uniform Reducts

Simple item page
dc.creatorCook, Stephen
dc.date2006-01-19
dc.date2006-01-23
dc.date.accessioned2026-07-07T06:57:59Z
dc.date.available2026-07-07T06:57:59Z
dc.descriptionArnold Beckmann defined the uniform reduct of a propositional proof system f to be the set of those bounded arithmetical formulas whose propositional translations have polynomial size f-proofs. We prove that the uniform reduct of f + Extended Frege consists of all true bounded arithmetical formulas iff f + Extended Frege simulates every proof system.
dc.identifierhttps://arxiv.org/abs/cs/0601086
dc.identifierhttp://arxiv.org/abs/cs/0601086
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/107182
dc.subjectComputational Complexity
dc.subjectF.4.1
dc.titleComments on Beckmann's Uniform Reducts
dc.typetext

Files

Collections

arXiv