AI-Complete, AI-Hard, or AI-Easy – Classification of Problems in AI

23rd Midwest Artificial Intelligence and Cognitive Science Conference 2012

Roman V. Yampolskiy

Others  :  http://ceur-ws.org/Vol-841/submission_3.pdf
PID  :  43716

来源: CEUR

【 摘 要 】

The paper contributes to the development of the theory of AI-Completeness by formalizing the notion of AI- Complete and AI-Hard problems. The intended goal is toprovide a classification of problems in the field of GeneralArtificial Intelligence. We prove Turing Test to be an instanceof an AI-Complete problem and further show numerous AIproblems to be AI-Complete or AI-Hard via polynomial timereductions. Finally, the paper suggests some directions for futurework on the theory of AI-Completeness.