Comments on Beckmann's Uniform Reducts

Preprint English OPEN
Cook, Stephen;
  • Subject: Computer Science - Computational Complexity | F.4.1
    arxiv: Computer Science::Logic in Computer Science

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 ... View more
Share - Bookmark