AI完全

AI完全（AIかんぜん、英: AI-complete）とは、人工知能のテーマの中でも最も困難なものを指す学術的でない用語である。AI完全とされる計算問題を解くことは人工知能の中心的課題を解決するのと同義であり、人間と同程度に知的なコンピュータを生み出すことになる。この用語は計算複雑性理論のNP完全問題などのアナロジーであり、計算複雑性理論における「完全性」とは、その複雑性クラスで最も難しい問題を指す。1988年、John Mallery はこの用語を生み出したのが Fanya S. Montalvo であると述べた。初期の用例としては、1987年に Erik Mueller の学位論文で使われ、1991年にはエリック・レイモンドのジャーゴンファイルに収録されている。

ある問題をAI完全であると呼ぶ場合、ELIZAのような単純なアルゴリズムを使った手法では解決されないだろうという姿勢が背景にある。一般にAI完全と言われる問題としては、次のものがある。

• コンピュータビジョン
• 自然言語理解
• チューリング・テストに合格すること

これらは人間にとっては簡単だが、その根幹には人間の持つ様々な概念が複雑に絡み合っていると言える。これらの問題を非常に制限された設定で解くシステムもあるが、完全な汎用性のある解法は未だに存在しない。

参考文献

• Engels, Robert & Bremdal, Bernt (2000, July 28). Information Extraction: State-of-the-Art Report.
• Mallery, John C. (1988). Thinking About Foreign Policy: Finding an Appropriate Role for Artificially Intelligent Computers The 1988 Annual Meeting of the International Studies Association. St. Louis, MO.
• Mueller, Erik T. (1987, March). Daydreaming and Computation (Technical Report CSD-870017) 学位論文、カリフォルニア大学ロサンゼルス校。("Daydreaming is but one more AI-complete problem: if we could solve any one artificial intelligence problem, we could solve all the others", p. 302) - 注意:スキャンした文書なので非常に大きい。
• Raymond, Eric S. (1991, March 22). Jargon File Version 2.8.1 （"AI-complete" が初めて追加されたバージョン）
• Shapiro, Stuart C. (1992). Artificial Intelligence In Stuart C. Shapiro (Ed.), Encyclopedia of Artificial Intelligence (Second Edition, pp. 54-57). New York: John Wiley. (Section 4 is on "AI-Complete Tasks".)