著者

井上 克巳

雑誌

情報処理

巻号頁・発行日

vol.57, no.8, pp.720-723, 2016-07-15

---

SATは計算機科学において最も単純で基本的な問題であるとともに,人工知能(AI)においても推論や制約充足のベースとなる重要な問題である.またSAT技術もアルゴリズム分野というよりは,AI研究の中で発展してきたことは注目に値する.本稿では,SATとAIの密接な関係を歴史的に概観し,SATがどれだけAIにインパクトを与えてきて,今後のAI 技術を左右し得るかについて予測する.SATは問題の構造が単純過ぎて(また理論的にもクラスNP に属するため)AIの本質的な複雑さには到底及ばないという意見があるにもかかわらず,SATの深遠さを知ることがAIに通ずることを本稿から読み取っていただきたい.