裳華房のtwitterをフォローする


オンライン書店の 『証明論と計算量』 購入ページへの直接リンク
amazonhonto楽天ブックスオムニ7BOOKFANe-honHonya Club
丸善 Knowledge Worker紀伊國屋書店TSUTAYA


証明論と計算量
Bounded Arithmetic and Computational Complexity

イリノイ大学名誉教授 理博 竹内外史 著
A5判/214頁/定価3780円(本体3500円+税8%)/1995年11月
ISBN978-4-7853-1096-7 (旧ISBN4-7853-1096-0)

 自然数論の証明論は数学基礎論の中心的問題であったが,弱い自然数論の証明論が計算量の理論と密接な関係にあることが知られている.本書は,証明論と計算量との中間領域についての基本的な事柄を,最近の話題を含めてまとめたものである.限定算術固有の分野には深入りせず,最近の目覚しい話題のFregeシステムについてふれた.

【目 次】

『証明論と計算量』 カバー
1  多項式時間で計算できる関数
 1.1 自然数
 1.2 多項式時間で計算可能な関数
 1.3 Turing machine

2  限定算術
 2.1 限定算術の体系
 2.2 Si2,Ti2の証明論
 2.3 Bussの定理

3  超数学の形式化と不完全性定理
 3.1 多項式時間の帰納的定義
 3.2 超数学の形式化
 3.3 不完全性定理

4  PHPと数え上げ原理
 4.1 命題論理体系FとEF
 4.2 PHPnとCountan
 4.3 ノンスタンダード・モデルの上の強制法

記号表



         

自然科学書出版 裳華房 SHOKABO Co., Ltd.