Arithmetic, proof theory, and computational complexity. (English) Zbl 0777.00008

Oxford Logic Guides. 23. Oxford: Clarendon Press. xii, 428 p. (1993).

Show indexed articles as search result.

The articles of this volume will be reviewed individually.
Indexed articles:
Open problems, 1-19 [Zbl 0794.03077]
Baaz, Matthias, Note on the existence of most general semi-unifiers, 20-29 [Zbl 0806.03036]
Baaz, Matthias; Pudlák, Pavel, Kreisel’s conjecture for \(L\exists_ 1\). (Including a postscript by Georg Kreisel), 30-60 [Zbl 0812.03024]
Bonet, Maria Luisa, Number of symbols in Frege proofs with and without the deduction rule, 61-95 [Zbl 0806.03038]
Buss, Samuel R., Algorithms for Boolean formula evaluation and for tree contraction, 96-115 [Zbl 0792.68046]
Buss, Samuel R.; Krajíček, Jan; Takeuti, Gaisi, Provably total function in bounded arithmetic theories \(R_ 3^ i\), \(U_ 2^ i\) and \(V_ 2^ i\), 116-161 [Zbl 0799.03065]
Clote, Peter, On polynomial size Frege proofs of certain combinatorial principles, 162-184 [Zbl 0793.03046]
Hájek, Petr, Interpretability and fragments of arithmetic, 185-196 [Zbl 0791.03033]
Hájek, Petr; Montagna, Franco; Pudlák, Pavel, Abbreviating proofs using metamathematical rules, 197-221 [Zbl 0794.03080]
Kaye, Richard, Open induction, Tennenbaum phenomena, and complexity theory, 222-237 [Zbl 0799.03067]
Kaye, Richard, Using Herbrand-type theorems to separate strong fragments of arithmetic, 238-246 [Zbl 0803.03038]
Razborov, Alexander A., An equivalence between second order bounded domain bounded arithmetic and first order bounded arithmetic, 247-277 [Zbl 0789.03046]
Ressayre, J.-P., Integer parts of real closed exponential fields, 278-288 [Zbl 0791.03018]
Riis, Søren, Making infinite structures finite in models of second order bounded arithmetic, 289-319 [Zbl 0794.03082]
Sommer, Richard, Ordinal arithmetic in \(I\Delta_ 0\), 320-363 [Zbl 0847.03026]
Takeuti, Gaisi, \(RSUV\) isomorphisms, 364-386 [Zbl 0792.03041]
Verbrugge, Rineke, Feasible interpretability, 387-428 [Zbl 0799.03068]

MSC:

00B15	Collections of articles of miscellaneous specific interest
03-06	Proceedings, conferences, collections, etc. pertaining to mathematical logic and foundations

Keywords:

Arithmetic; Proof theory; Computational complexity