![](https://d3ilqtpdwi981i.cloudfront.net/6VacdHQfro1yCgKuInDJIQtFmQw=/425x550/smart/https://bepress-attached-resources.s3.amazonaws.com/uploads/29/25/8e/29258ed4-4ab4-4ce2-9748-c91f60efe10c/thumbnail_5e36c060-bcf1-4810-8f36-cf27fa57fc4f.jpg)
The paper contributes to the development of the theory of AI-Completeness by formalizing the notion of AI-Complete, C-Complete and AI-Hard problems. The intended goal is to provide a classification of problems in the field of Artificial General 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.
Yampolskiy R.V. (2013) Turing Test as a Defining Feature of AI-Completeness. In: Yang XS. (eds) Artificial Intelligence, Evolutionary Computing and Metaheuristics. Studies in Computational Intelligence, vol 427. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29694-9_1