AI-complete, AI-hard, or AI-easy - Classification of problems in AI
Abstract
The paper contributes to the development of the theory of AI-Completeness by formalizing the notion of AIComplete 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 numerous 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.
This paper has been withdrawn.
