Towards a Theory of AI Completeness

Dafna Shahaf, Eyal Amir

In this paper we present a novel classification of computational 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.

Subjects: 9.3 Mathematical Foundations; 9.2 Computational Complexity

Submitted: Jan 26, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.