AI-완전

AI-완전 (영: AI-complete)은 인공지능의 테마 중에서도 가장 곤란한 것을 가리키는 학술적이지 않은 용어이다. AI-완전으로 여겨지는 계산 문제를 푸는 것은 인공지능의 중심적 과제를 해결하는 것과 동의이며, 인간과 동일한 정도로 지적인 컴퓨터를 낳게 된다. 이 용어는 계산 복잡도 이론의 NP-완전 등의 유추이며, 계산 complex system 이론에서의 '완전성'이란, 그 복잡도 종류에서 가장 어려운 문제를 가리킨다. 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 Archived 2008년 2월 29일 - 웨이백 머신 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".)