Arithmetic, Proof Theory, and Computational Complexity by Peter CloteArithmetic, Proof Theory, and Computational Complexity by Peter Clote

Arithmetic, Proof Theory, and Computational Complexity

EditorPeter Clote, Jan Krajicek

Hardcover | January 1, 1994

Pricing and Purchase Info


Earn 1,875 plum® points

Prices and offers may vary in store


In stock online

Ships free on orders over $25

Not available in stores


This book principally concerns the rapidly growing area of what might be termed "Logical Complexity Theory", the study of bounded arithmetic, propositional proof systems, length of proof, etc and relations to computational complexity theory. Issuing from a two-year NSF and Czech Academy ofSciences grant supporting a month-long workshop and 3-day conference in San Diego (1990) and Prague (1991), the book contains refereed articles concerning the existence of the most general unifier, a special case of Kreisel's conjecture on length-of-proof, propositional logic proof size, a newalternating logtime algorithm for boolean formula evaluation and relation to branching programs, interpretability between fragments of arithmetic, feasible interpretability, provability logic, open induction, Herbrand-type theorems, isomorphism between first and second order bounded arithmetics,forcing techniques in bounded arithmetic, ordinal arithmetic in L D o . Also included is an extended abstract of J P Ressayre's new approach concerning the model completeness of the theory of real closed expotential fields. Additional features of the book include (1) the transcription andtranslation of a recently discovered 1956 letter from K Godel to J von Neumann, asking about a polynomial time algorithm for the proof in k-symbols of predicate calculus formulas (equivalent to the P-NP question), (2) an OPEN PROBLEM LIST consisting of 7 fundamental and 39 technical questionscontributed by many researchers, together with a bibliography of relevant references.
Peter Clote is at Boston College, . Jan Krajicek is at Ceskoslovenska Akademie Ved Praha 1.
Title:Arithmetic, Proof Theory, and Computational ComplexityFormat:HardcoverDimensions:442 pages, 9.21 × 6.14 × 1.18 inPublished:January 1, 1994Publisher:Oxford University Press

The following ISBNs are associated with this title:

ISBN - 10:0198536909

ISBN - 13:9780198536901

Look for similar items by category:


Table of Contents

Preface1. Open Problems2. Matthias Baaz: Note on the Existence of Most General Semi-unifiers3. Matthias Baaz and Pavel Pudlak: Kreisel's Conjecture for L31 (including a postscript by George Kreisel)4. Maria Luisa Bonet: Number of Symbols in Frege Proofs with and without the Deduction Rule5. Samuel R. Buss: Algorithm for Boolean Formula Evolution and for Tree Contraction6. Samuel R. Buss, Jan Kraj"icek and Gaisi Takeuti: Provably Total Functions in Bounded Arithmetic Theories Ri3, Ui2 and Vi27. Peter Clote: On Polynomial Size Frege Proofs of Certain Combinatorial Principles8. Petr Hajek: Interpretability and Fragments of arithmetic9. Petr Hajek, Franco Montagna and Pavel Pudlak: Abbreviating Proofs Using Metamathematical Rules10. Richard Kaye: Open Induction, Tennenbaum Phenomena, and Complexity Theory11. Richard Kaye: Using Herbrand-type Theorems to Separate Strong Fragments of Arithmetic12. Alexander A. Razborov: An Equivalence between Second Order Bounded Domain Bounded Arithmetic and First Order Bounded Arithmetic13. Jean-Pierre Ressayre: Integer Parts of Real Closed Exponential Fields (extended abstract)14. Soren Riis: Making Infinite Structures Finite in Models of Second Order Bounded Arithmetic15. Richard Sommer: Ordinal Arithmetic in I16. Gaisi Takeuti: RSUV Isomorphism17. Rineke Verbrugge: Feasible Interpretability

Editorial Reviews

`The book is on the level of a graduate course, and in this is superb. A highly recommendable book.'Mededelingen van Het Wiskundig Genootschaap, September 1996