Clote, Krajicek

Arithmetic, Proof Theory, and Computational Complexity

Herausgeber: Clote, Peter

• Gebundenes Buch

Produktbeschreibung

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, and similar themes, and the relations of these topics to computational complexity theory. Issuing from a two-year international collaboration, the book contains 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 new alternating 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, and 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 exponential fields. Additional features of the book include the transcription and translation of a recently discovered 1956 letter from Kurt 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); and an open problem list consisting of seven fundamental and 39 technical questions contributed by many researchers, together with a bibliography of relevant references. This scholarly work will interest mathematical logicians, proof and recursion theorists, and researchers in computational complexity.

Produktdetails

• Verlag: Sydney University Press
• Seitenzahl: 442
• Erscheinungstermin: 10. Juni 1993
• Englisch
• Abmessung: 229mm x 152mm x 29mm
• Gewicht: 816g
• ISBN-13: 9780198536901
• ISBN-10: 0198536909
• Artikelnr.: 21362122

Inhaltsangabe

* Preface
* 1: Open Problems
* 2: Matthias Baaz: Note on the Existence of Most General Semi-unifiers
* 3: Matthias Baaz and Pavel Pudlák: 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 Rule
* 5: Samuel R. Buss: Algorithm for Boolean Formula Evolution and for
Tree Contraction
* 6: Samuel R. Buss, Jan Kraj^"icek and Gaisi Takeuti: Provably Total
Functions in Bounded Arithmetic Theories Ri3, Ui2 and Vi2
* 7: Peter Clote: On Polynomial Size Frege Proofs of Certain
Combinatorial Principles
* 8: Petr Hájek: Interpretability and Fragments of arithmetic
* 9: Petr Hájek, Franco Montagna and Pavel Pudlák: Abbreviating Proofs
Using Metamathematical Rules
* 10: Richard Kaye: Open Induction, Tennenbaum Phenomena, and
Complexity Theory
* 11: Richard Kaye: Using Herbrand-type Theorems to Separate Strong
Fragments of Arithmetic
* 12: Alexander A. Razborov: An Equivalence between Second Order
Bounded Domain Bounded Arithmetic and First Order Bounded Arithmetic
* 13: Jean-Pierre Ressayre: Integer Parts of Real Closed Exponential
Fields (extended abstract)
* 14: Søren Riis: Making Infinite Structures Finite in Models of Second
Order Bounded Arithmetic
* 15: Richard Sommer: Ordinal Arithmetic in I
* 16: Gaisi Takeuti: RSUV Isomorphism
* 17: Rineke Verbrugge: Feasible Interpretability