Proof complexity and feasible arithmetics : DIMACS workshop, April 21-24, 1996 / Paul W. Beame, Samuel R. Buss, editors.

Format Book
Publication InfoProvidence, R.I. : American Mathematical Society, ©1998.
Descriptionxii, 320 pages : illustrations ; 26 cm.
Subjects
Proof theory--Congresses.
Constructive mathematics--Congresses.
Computational complexity--Congresses.

Other author/creatorBeame, Paul W., 1959-
Other author/creatorBuss, Samuel R.
Other author/creatorDIMACS series in discrete mathematics and theoretical computer science.
Other author/creatorNSF Science and Technology Center in Discrete Mathematics and Theoretical Computer Science.
Other author/creatorDIMACS Workshop on Feasible Arithmetics and Length of Proofs (1996 : Rutgers University)
SeriesDIMACS series in discrete mathematics and theoretical computer science ; v. 39
DIMACS series in discrete mathematics and theoretical computer science ; v. 39. ^A467230
Contents Plausibly hard combinatorial tautologies / Jeremy Avigad -- More on the relative strength of counting principles / Paul Beame and Søren Riis -- Ranking arithmetic proofs by implicit ramification / Stephen J. Bellantoni -- Lower bounds on Nullstellensatz proofs via designs / Samuel R. Buss -- Relating the provable collapse of P to NC¹ and the power of logical theories / Stephen Cook -- On PHP st-connectivity, and odd charged graphs / Peter Clote and Anton Setzer -- Descriptive complexity and the W hierarchy / Rodney G. Downey, Michael R. Fellows, and Kenneth W. Regan -- Lower bounds on the sizes of cutting plane proofs for modular coloring principles / Xudong Fu -- Equational calculi and constant depth propositional proofs / Jan Johannsen -- Exponential lower bounds for semantic resolution / Stasys Jukna -- Bounded arithmetic : comparison of Buss' witnessing method and Sieg's Herbrand analysis / Barbara Kauffmann -- Towards lower bounds for bounded-depth Frege proofs with modular connectives / Alexis Maciel and Toniann Pitassi -- A quantifier-free theory based on a string algebra for NC¹ / François Pitt -- A propositional proof system for R₂ / Chris Pollett --Algebraic models of computation and interpolation for algebraic proof systems / Pavel Pudlák and Jir̆í Sgall -- Self-reflection principles and NP-hardness / Dan E. Willard.
General note"NSF Science and Technology Center in Discrete Mathematics and Theoretical Computer Science, a consortium of Rutgers University, Princeton University, AT&T Labs, Bell Labs, and Bellcore."
General notePapers from the proceedings of the DIMACS Workshop on Feasible Arithmetics and Length of Proofs, held on April 21-24, 1996 at Rutgers, New Jersey.
Bibliography noteIncludes bibliographical references.
LCCN 97029122
ISBN0821805770 (alk. paper)

Availability

Library Location Call Number Status Item Actions
Joyner General Stacks QA9.54 .P75 1998 ✔ Available Place Hold