AI-complete In the field of artificial intelligence, the most difficult problems are informally known as AI-complete or AI-hard, implying that the difficulty of these computational problems is equivalent to solving the central artificial intelligence problem—making computers as intelligent as people, or strong AI.
The term was coined by Fanya Montalvo by analogy with NP-complete and NP-hard in complexity theory, which formally describes the most famous class of difficult problems. Early uses of the term are in Erik Mueller’s 1987 Ph.D. dissertation and in Eric Raymond’s 1991 Jargon File.
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 (and subproblems such as object recognition)
Natural language understanding (and subproblems such as text mining, machine translation, and word sense disambiguation)
Dealing with unexpected circumstances while solving any real world problem, whether it’s navigation or planning or even the kind of reasoning done by expert systems.
