証明論と計算量 の商品レビュー

竹内外史(著者)

2012/01/14

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

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

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

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

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