AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Proof Complexity and Feasible Arithmetics
About this Title
Paul W. Beame, University of Washington, Seattle, WA and Samuel R. Buss, University of California at San Diego, La Jolla, CA, Editors
Publication: DIMACS Series in Discrete Mathematics and Theoretical Computer Science
Publication Year:
1998; Volume 39
ISBNs: 978-0-8218-0577-0 (print); 978-1-4704-3997-2 (online)
DOI: https://doi.org/10.1090/dimacs/039
MathSciNet review: MR1486610
MSC: Primary 03F20; Secondary 03-06, 03F30, 68-06, 68Q15
Table of Contents
Front/Back Matter
Chapters
- Plausibly hard combinatorial tautologies
- More on the relative strength of counting principles
- Ranking arithmetic proofs by implicit ramification
- Lower bounds on Nullstellensatz proofs via designs
- Relating the provable collapse of $\mathbf P$ to ${\mathbf NC}^1$ and the power of logical theories
- On $PHP$, $st$-connectivity, and odd charged graphs
- Descriptive complexity and the $W$ hierarchy
- Lower bounds on sizes of cutting plane proofs for modular coloring principles
- Equational calculi and constant depth propositional proofs
- Exponential lower bounds for semantic resolution
- Bounded arithmetic: Comparison of Buss’ witnessing method and Sieg’s Herbrand analysis
- Towards lower bounds for bounded-depth Frege proofs with modular connectives
- A quantifier-free theory based on a string algebra for $NC^1$
- A propositional proof system for $R^i_2$
- Algebraic models of computation and interpolation for algebraic proof systems
- Self-reflection principles and NP-hardness