複雑性と情報

「情報に基づく複雑性理論（IBC)という連続問題の複雑性を解析する分野に関する最近の成果を、入門者でもわかるようにまとめたもの。IBCとは、手に入る情報が部分的で汚れており、かつ有償であるような問題の計算複雑性を研究する学問である。ハイライトはここ数年、注目をあつめている「多重数値積分アルゴリズムとその金融工学への応用」に関する重要な成果で、多くのページを費やしている。コロンビア大学では、この成果をFINDERという製品名で販売せいおり、ウォール街で使われている。一部ではIBCに関する分かりやすい 解説を、二部ではコロンビア大学でなされた仕事を中心に、興味ある話題を取り揃えた。三部では、400を越える最新の文献を収録した。