Substitution and Propositional Proof Complexity

DOI10.1007/978-3-030-71430-7_17OpenAlexW3203190072MaRDI QIDQ5027247

Samuel R. Buss

Publication date: 4 February 2022

Published in: Outstanding Contributions to Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-71430-7_17

zbMATH Keywords

lower boundsFregeproof complexitysubstitutionBegriffsschriftFrege proofGrundgesetzemultisubstitution

Mathematics Subject Classification ID

General logic (03Bxx) Algebraic logic (03Gxx)

Cites Work

• Russell's substitutional theory
• The number of lines in Frege proofs with substitution
• Some remarks on lengths of propositional proofs
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• The relative efficiency of propositional proof systems
• Proof Complexity
• The Russell Archives: Some new light on Russell's logicism
• What Types Should Not Be†
• Essays on Frege's Basic Laws of Arithmetic
• A new hypothesis to account for the red-shift in the spectra of distant stars
• The Complexity of Propositional Proofs with the Substitution Rule
• Banishing the rule of substitution for functional variables
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Substitution and Propositional Proof Complexity