AI-complete

From Wikipedia, the free encyclopedia

AI-complete is an informal phrase describing the most difficult class of artificial intelligence problems. The difficulty of these computational problems is equivalent to solving the central artificial intelligence problem, in other words, making computers as intelligent as people. The term was coined by Fanya S. Montalvo using an analogy to NP-completeness in complexity theory, which formally describes the most famous class of difficult problems.

To call a problem AI-complete reflects an attitude that it won't be solved by a simple algorithm, such as those used in ELIZA. Such problems are hypothesised to include:

• Computer vision
• Natural language understanding
• Passing the Turing Test

These problems are easy for humans to do (in fact, some are described directly in terms of imitating humans), and all, at their core, are about representing complex relationships between a large number of human concepts. Some systems can solve very simple restricted versions of these problems, but none can solve them in their full generality.

[edit] References

• Robert Engels & Bernt Bremdal Information Extraction: State-of-the-Art Report July 28, 2000.
• Mallery, J.C.M. Thinking About Foreign Policy: Finding an Appropriate Role for Artificially Intelligent Computers. The 1988 Annual Meeting of the International Studies Association, St. Louis, Missouri.