証明論と計算量

著者 : 竹内外史

• 裳華房 (1995年11月10日発売)

作品紹介・あらすじ

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

感想・レビュー・書評

[kaizenさんの感想 · 2012年1月14日]

証明にかかる計算量について知りたくて手に取りました。
多項式時間で計算できる関数というものがあることはわかりました。

また、PHPが pigeon hole principleの略であり、
N+1羽の鳩がN個の巣に入っていれば、ある巣の中には、少なくとも２羽の鳩が入っている。
話であることも分かりました。

ただ、実際に鳩と穴との関係であれば、出入りをするはずであるし、
出入りの時間の問題もあるだろうから、

出入りをしない静的な課題というのは、より複雑な問題を解くための
基礎だということが推測しています。

厳密に証明しようとおもうと、手間が大変だし、
計算量を求めようと思うと、なかなか大変だなと感じました。

著者プロフィール

イリノイ大学名誉教授、理学博士。1926年 石川県に生まれる。東京大学理学部卒業。東京大学講師、東京教育大学助教授・教授、イリノイ大学教授などを歴任。主な著書に『リー代数と素粒子論』『線形代数と量子力学』（以上 裳華房）、『現代集合論入門』『層・圏・トポス』（以上 日本評論社）、『直観主義的集合論』（紀伊國屋書店）などがある。

「1995年 『証明論と計算量』 で使われていた紹介文から引用しています。」