Towards a Theory of AI Completeness

Abstract

In this paper we present a novel classification of compu-tational problems. Motivated by a theoretical investigation of Artificial Intelligence (AI), we present (1) a complexity model for computational problems that includes a human in the process, and (2) a classification of prototypical problems treated in the AI literature. The contribution of this paper is useful for automatically distinguishing between human and computer users. Also, this work serves as a formal basis for investigation of problems that researchers treat as hard AI problems. Most importantly, this work allows progress in AI as a field to be more measurable, instead of measurable with respect to problem-specific quantities. 1