Reprinted with permission from Roman V. Yampolskiy, Ph.D
Abstract. The paper contributes to developing the theory of AI-completeness 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 the 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.
Table of contents
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 extending the work in [56] and contributing to the theory of AI-completeness, a formalism designed to do for the field of AI what the notion of NP-completeness did for computer science in general. We believe such formalization will allow even faster progress in solving the remaining problems in humankind’s conquest to build an intelligent machine.
According to Wikipedia, the term “AI-Complete” was proposed by Fanya Montalvo in the 1980s. A somewhat general definition of the term included in the 1991 Jargon File 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 the strong 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 of AI-complete problems are The Vision Problem, which is building a system that can see as well as a human, and The Natural Language Problem, which is building a system that can understand and speak a natural language and a human. These may appear modular, but all attempts (1991) to solve them have foundered on the amount of context information and `intelligence’ they seem to require.
Summary of AI-Completeness
The idea is that all of the human brain’s computing power completing any function is the basis of a Human Oracle (HO). It can be thought of as modelling the cognitive abilities of humans in a computational framework. The HO is designed to compute any function that can be performed by the collective cognitive abilities of all human minds. Two variants are proposed:
- HumanBest: Represents the cognitive peak, capturing the best possible human solution for any problem.
- HumanAverage: Computes the average decision made by many human minds for a given input, converging as the number of participants increases.
The HO function takes an input string and returns an output string, without specifying the data format (it could be binary or natural language). It can integrate with modern programming languages and call regular Turing Machine (TM) functions for data processing, potentially displaying input as images to aid human understanding.
This model can also be formalized using Human-Assisted Turing Machines (HTM), where humans act as oracle machines that decide language sets in constant or variable time. The model includes probabilistic oracles (providing answers with certain probabilities) and introduces the notion of reward to capture improved human performance on incentivized tasks.
While intuitive, this model requires formalization to represent human cognitive diversity in computational tasks fully. In this paper, Yampolskiy seeks to use the Turing Test, which is AI-complete.
