Arithmetic, proof theory, and computational complexity
Author(s)
Bibliographic Information
Arithmetic, proof theory, and computational complexity
（Oxford logic guides, 23）
Clarendon Press, 1993
Available at 41 libraries
-
Library, Research Institute for Mathematical Sciences, Kyoto University数研
C-P||San Diego & Prague||1990 & 199193020262
Note
Includes references
Description and Table of Contents
Description
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 of Sciences 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 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, ordinal arithmetic in 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 and translation 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 questions contributed by many researchers, together with a bibliography of relevant references.
Table of Contents
- Preface
- 1. Open Problems
- 2. Note on the Existence of Most General Semi-unifiers
- 3. Kreisel's Conjecture for L31 (including a postscript by George Kreisel)
- 4. Number of Symbols in Frege Proofs with and without the Deduction Rule
- 5. Algorithm for Boolean Formula Evolution and for Tree Contraction
- 6. Provably Total Functions in Bounded Arithmetic Theories Ri3, Ui2 and Vi2
- 7. On Polynomial Size Frege Proofs of Certain Combinatorial Principles
- 8. Interpretability and Fragments of arithmetic
- 9. Abbreviating Proofs Using Metamathematical Rules
- 10. Open Induction, Tennenbaum Phenomena, and Complexity Theory
- 11. Using Herbrand-type Theorems to Separate Strong Fragments of Arithmetic
- 12. An Equivalence between Second Order Bounded Domain Bounded Arithmetic and First Order Bounded Arithmetic
- 13. Integer Parts of Real Closed Exponential Fields (extended abstract)
- 14. Making Infinite Structures Finite in Models of Second Order Bounded Arithmetic
- 15. Ordinal Arithmetic in I
- 16. RSUV Isomorphism
- 17. Feasible Interpretability
by "Nielsen BookData"