Reprinted with permission from Roman V. Yampolskiy, Ph.D
Abstract. The paper contributes to the development of the theory of AICompleteness by formalizing the notion of AI-Complete and AI-Hard problems.
The intended goal is to provide a classification of problems in the field of General Artificial Intelligence. We prove Turing Test to be an instance of an AI-Complete problem and further show certain AI problems to be AI-Complete or AI-Hard via polynomial time reductions. Finally, the paper suggests some directions for future work on the theory of AI-Completeness.
Keywords: AI-Complete, AI-Easy, AI-Hard, Human Oracle.
1 Introduction
Since its inception in the 1950s the field of Artificial Intelligence has produced some unparalleled accomplishments while at the same time failing to formalize the problem space it is concerned with. This paper proposes to address this shortcoming by extends on the work in [56] and contributing to the theory of AICompleteness, a formalism designed to do for the field of AI what notion of NP-Completeness did for computer science in general. It is our belief that such formalization will allow for even faster progress in solving remaining problems in humankind’s conquest to build an intelligent machine.
According to the encyclopedia Wikipedia the term “AI-Complete” was proposed by Fanya Montalvo in the 1980s [54]. A somewhat general definition of the term included in the 1991 Jargon File [37] states:
“AI-Complete: [MIT, Stanford, by analogy with NP-complete'] adj. Used to describe problems or subproblems in AI, to indicate that the solution presupposes a solution to thestrong AI problem’ (that is, the synthesis of a human-level intelligence). A problem that is AI-complete is, in other words, just too hard. Examples…
