証明論と計算量

竹内外史(著者)

• 販売会社／発売会社: 裳華房/
• 発売年月日: 1995/11/10
• JAN: 9784785310967

商品レビュー

2012/01/14

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

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

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

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

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