publication . Preprint . 2006

Comments on Beckmann's Uniform Reducts

Cook, Stephen;
Open Access English
  • Published: 19 Jan 2006
Abstract
Arnold 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.
Subjects
arXiv: Computer Science::Logic in Computer Science
free text keywords: Computer Science - Computational Complexity, F.4.1
Download from

[Bec05] Arnold Beckmann. Uniform proof complexity. to appear in J. Logic and Computation, 2005.

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue