指数時間アルゴリズムというのは,NP困難問題を頑張って指数時間かけて解くアルゴリズムのことで,できるだけ指数の底の小さいアルゴリズムを開発することが目指されています. コンテスト界では部分和問題の半分全列挙による2^(n/2)時間アルゴリズムなどが特に有名だと思います. この分野は近年盛んに研究され始め,自分も大学でこの分野を中心に研究をしています. 今回,情報オリンピック春合宿講義とPFIセミナーで発表する機会があったので,この分野の基礎的な手法から最先端の手法までをまとめてみました. 指数時間アルゴリズム入門@情報オリンピック春合宿講義 http://www.slideshare.net/wata_orz/ss-12131479 指数時間アルゴリズムの最先端(キャンセリング)@PFIセミナー http://www.slideshare.net/wata_orz/ss-12208032