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  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".)

인공지능
계산 문제