Propositional Proofs in Frege and Extended Frege Systems (Abstract)

DOI10.1007/978-3-319-20297-6_1zbMath1464.03087OpenAlexW1054254092MaRDI QIDQ3194704

Samuel R. Buss

Publication date: 20 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-20297-6_1

zbMATH Keywords

bounded arithmeticproof complexityFrege proofspigeonhole principleKneser-Lovász theorem

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Complexity of proofs (03F20)

Cites Work

• Propositional proofs and reductions between NP search problems
• The provably total NP search problems of weak second order bounded arithmetic
• Kneser's conjecture, chromatic number, and homotopy
• Propositional consistency proofs
• A combinatorical proof of Kneser's conjecture
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Quasipolynomial size proofs of the propositional pigeonhole principle
• QUASIPOLYNOMIAL SIZE FREGE PROOFS OF FRANKL’S THEOREM ON THE TRACE OF SETS
• Proof Complexity and the Kneser-Lovász Theorem
• Short Proofs of the Kneser-Lovász Coloring Principle
• Twelve Problems in Proof Complexity
• Polynomial size proofs of the propositional pigeonhole principle
• The relative efficiency of propositional proof systems
• Short Proofs for the Determinant Identities
• Improved witnessing and local improvement principles for second-order bounded arithmetic
• The Complexity of Propositional Proofs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Propositional Proofs in Frege and Extended Frege Systems (Abstract)