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 that of solving the central artificial intelligence problem—making computers as intelligent as people, or strong AI. To call a problem AI-complete reflects an attitude that it would not be solved by a simple specific algorithm, but a whole model of Intelligence.

Currently, AI-complete problems cannot be solved with modern computer technology alone, but would also require human computation. This property can be useful, for instance to test for the presence of humans as with CAPTCHAs, and for computer security to circumvent brute-force attacks.

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.

Formalization

Computational complexity theory deals with the relative computational difficulty of computable functions. By definition it does not cover problems whose solution is unknown or has not been characterised formally. Since many AI problems have no formalisation yet, conventional complexity theory does not allow the definition of AI-completeness.

To address this problem, a complexity theory for AI has been proposed. It is based on a model of computation that splits the computational burden between a computer and a human: one part is solved by computer and the other part solved by human. This is formalised by a human-assisted Turing machine. The formalisation defines algorithm complexity, problem complexity and reducibility which in turn allows equivalence classes to be defined.

The complexity of executing an algorithm with a human-assisted Turing machine is given by a pair ${\displaystyle \langle \Phi _{H},\Phi _{M}\rangle }$, where the first element represents the complexity of the human’s part and the second element is the complexity of the machine’s part.

See also

Artificial Intelligence

Material

• http://www.i-programmer.info/babbages-bag/297-artificial-intelligence.html

Papers

• Dafna Shahaf and Eyal Amir (2007) Towards a theory of AI completeness. Commonsense 2007, 8th International Symposium on Logical Formalizations of Commonsense Reasoning.
• Nelson Morgan et al., MEETINGS ABOUT MEETINGS: RESEARCH AT ICSI ON SPEECH IN MULTIPARTY CONVERSATIONS, In: ICASSP 2003, April 6-10, 2003.
• Yang, Xin-She, ed. Artificial intelligence, evolutionary computing and metaheuristics: in the footsteps of Alan Turing. Vol. 427. Springer, 2012.

Books

• Shapiro, Stuart C. (1992). Encyclopedia of Artificial Intelligence. 2nd Edition, John Wiley. (Section 4 is on “AI-Complete Tasks”.)