Games, Puzzles, & Computation

Games, Puzzles, and Computation

Bob Hearnの博士論文をもとにした本．WADSでErik Demaineが紹介していたので即注文したらもう届いていた．最後の参考文献のところを見ているとこの分野に対する日本人の貢献が大きいことも分かる．日本人 (と思われる人) の名前を全部抽出すると，Hiroyuki Adachi, Shigeki Iwata, Hiroyuki Kamekawa, Takumi Kasai, Tomohiro Kitagawa, Masashi Kiyomi, Gembu Morohashi, Tadaaki Nagao, Takahiro Seta, Tatsuie Tsukiji, Nobuhisa Ueda, Ryuhei Uehara, Takeaki Uno, Takayuki Yato, Masaya Yokotaとなる．抜けてる方がいましたらすいません．

内容は，いろいろな種類のゲームやパズルの難しさを計算量理論の観点からどのように証明し，その統一的な構造は何なのかを明らかにしようと試みている．未解決問題集も載っているので研究者には嬉しい．