0845 474 4572
info@eurospanbookstore.com

Special order: Usually despatched within 10-14 days

# Proof Complexity and Feasible Arithmetics

ISBN: 9780821805770

Publication Date: Nov 1997

Format: Hardback

Contains papers that represent the proceedings of the DIMACS workshop on 'Feasible Arithmetics and Proof Complexity' held in April 1996 at Rutgers University in New Jersey as part of the DIMACS Institute's Special Year on Logic and Algorithms. This book covers a number of aspects of the field, including lower bounds in proof complexity.
£73.50

Special order: will dispatch within 5 days

• Full Description
Plausibly hard combinatorial tautologies by J. Avigad More on the relative strength of counting principles by P. Beame and S. Riis Ranking arithmetic proofs by implicit ramification by S. J. Bellantoni Lower bounds on Nullstellensatz proofs via designs by S. R. Buss Relating the provable collapse of $\mathbfP$ to $\mathrm {NC}^1$ and the power of logical theories by S. Cook On $PHP$, $st$-connectivity, and odd charged graphs by P. Clote and A. Setzer Descriptive complexity and the $W$ hierarchy by R. G. Downey, M. R. Fellows, and K. W. Regan Lower bounds on the sizes of cutting plane proofs for modular coloring principles by X. Fu Equational calculi and constant depth propositional proofs by J. Johannsen Exponential lower bounds for semantic resolution by S. Jukna Bounded arithmetic: Comparison of Buss' witnessing method and Sieg's Herbrand analysis by B. Kauffmann Towards lower bounds for bounded-depth Frege proofs with modular connectives by A. Maciel and T. Pitassi A quantifier-free theory based on a string algebra for $NC^1$ by F. Pitt A propositional proof system for $R^i_2$ by C. Pollett Algebraic models of computation and interpolation for algebraic proof systems by P. Pudlak and J. Sgall Self-reflection principles and NP-hardness by D. E. Willard.