<図書>
Arithmetic, proof theory, and computational complexity
責任表示 | edited by Peter Clote and Jan Krajíček |
---|---|
シリーズ | Oxford logic guides ; 23 |
データ種別 | 図書 |
出版者 | Oxford : Clarendon Press |
出版年 | 1993 |
本文言語 | 英語 |
大きさ | xii, 428 p. : port. ; 25 cm |
概要 | 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 ...hemes, 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. 続きを見る |
所蔵情報
状態 | 巻次 | 所蔵場所 | 請求記号 | 刷年 | 文庫名称 | 資料番号 | コメント | 予約・取寄 | 複写申込 | 自動書庫 |
---|---|---|---|---|---|---|---|---|---|---|
|
中央図 3E | 410.1/C 791/1 | 1993 |
|
068582193012918 |
|
||||
|
理系図 自動書庫 | E4/Cl/1993 | 1993 |
|
061232004045363 |
|
書誌詳細
一般注記 | Includes references |
---|---|
著者標目 | Clote, Peter Krajíček, Jan |
件 名 | LCSH:Proof theory LCSH:Computational complexity LCSH:Arithmetic |
分 類 | LCC:QA9.54 DC20:511.3 |
書誌ID | 1001140889 |
ISBN | 0198536909 |
NCID | BA20017713 |
巻冊次 | ISBN:0198536909 |
登録日 | 2009.09.17 |
更新日 | 2009.09.17 |