Arithmetic, proof theory, and computational complexity

by Clote, Peter Krajícek, Jan

Type Book

Rate 0.0 /5

Details

Files

Reviews

Download

Title Statements

Full title :Arithmetic, proof theory, and computational complexity / edited by Peter Clote and Jan Krajíček.

Edition Statements

Publication Date:©1993.

Publication Statements

Publisher(s):Clarendon Press, Oxford University Press
Place of Publication:Oxford [England]
Language:eng
Publication Date:©1993.

The Physical Object

Description:xii, 428 pages : : illustrations ; : 25 cm.

Edition Identifiers

ISBN:0198536909, 9780198536901, 0820519650, 9780820519654
oclc:ocm27070235
LC Classification:QA9.54
Dewey Decimal:511.3

Note on the existence of most general semi-unifiers / Matthias Baaz -- Kreisel's conjecture for L[backwards E]₁ (including a postscript by Georg Kreisel) / Matthias Baaz and Pavel Pudlák -- Number of symbols in Frege proofs with and without the deduction rule / Maria Luisa Bonet -- Algorithm for Boolean formula evaluation and for tree contraction / Samuel R. Buss -- Provably total functions in bounded arithmetic theories R₃, U₂ and V₂ / Samuel R. Buss, Jan Krajíc̆ek and Gaisi Takeuti -- On polynomial size Frege proofs of certain combinatorial principles / Peter Clote -- Interpretability and fragments of arithmetic / Petr Hájek -- Abbreviating proofs using metamathematical rules / Petr Hájek, Franco Montagna and Pavel Pudlák -- Open induction, Tennenbaum phenomena, and complexity theory / Richard Kaye -- Using Herbrand-type theorems to separate strong fragments of arithmetic / Richard Kaye -- An equivalence between second order bounded domain bounded arithmetic and first order bounded arithmetic / Alexander A. Razborov -- Integer parts of real closed exponential fields (extended abstract) / Jean-Pierre Ressayre -- Making infinite structures finite in models of second order bounded a…

Subjects

algoritmen Bewijstheorie Complexite Complexité de calcul (Informatique) Computational complexity Mathematical logic mathematics Preuve, Théorie de la Proof theory Recursie Symbolische logica Théorie de la preuve théorie démonstration théorie nombre