Editing AI-complete (section)

==Research==
[[Roman Yampolskiy]]<ref>{{Citation |last=Yampolskiy |first=Roman |title=AI-Complete, AI-Hard, or AI-Easy – Classification of Problems in AI |date=2012 |work=23rd Midwest Artificial Intelligence and Cognitive Science Conference, MAICS 2012, Cincinnati, Ohio, USA, 21-22 April 2012  |url=https://www.proceedings.com/content/022/022437webtoc.pdf |access-date=2024-04-05 |language=en}}</ref>
suggests that a problem <math>C</math> is '''AI-Complete''' if it has two properties:
* It is in the set of AI problems (Human Oracle-solvable).
* Any AI problem can be converted into <math>C</math> by some polynomial time algorithm.
On the other hand, a problem <math>H</math> is '''AI-Hard''' if and only if there is an AI-Complete problem <math>C</math> that is polynomial time Turing-reducible to <math>H</math>. This also gives as a consequence the existence of '''AI-Easy''' problems, that are solvable in polynomial time by a deterministic Turing machine with an oracle for some problem.

Yampolskiy<ref>{{Citation |last=Yampolskiy |first=Roman |title=Turing Test as a Defining Feature of AI-Completeness
 |date=2013 |work=Artificial Intelligence, Evolutionary Computing and Metaheuristics |series=Studies in Computational Intelligence |volume=427 |pages=3–17 |language=en |doi=10.1007/978-3-642-29694-9_1|isbn=978-3-642-29693-2 }}</ref> has also hypothesized that the [[Turing Test]] is a defining feature of AI-completeness.

Groppe and Jain<ref>{{Citation |last1=Groppe |first1=Sven |first2=Sarika | last2=Jain |title=The Way Forward with AI-Complete Problems |date=2024 |journal=New Generation Computing|volume=42 |pages=1–5 |language=en |doi=10.1007/s00354-024-00251-8}}</ref> classify problems which require [[artificial general intelligence]] to reach human-level machine performance as AI-complete, while only restricted versions of AI-complete problems can be solved by the current AI systems. For Šekrst,<ref name="Sekrst2020" /> getting a polynomial solution to AI-complete problems would not necessarily be equal to solving the issue of artificial general intelligence, while emphasizing the lack of [[computational complexity]] research being the limiting factor towards achieving artificial general intelligence.

For Kwee-Bintoro and Velez,<ref>{{Citation |last1=Kwee-Bintoro |first1=Ted | last2 = Velez | first2 = Noah |title=AI-Complete: What it Means to Be Human in an Increasingly Computerized World |date=2022 |work=Bridging Human Intelligence and Artificial Intelligence |series=Educational Communications and Technology: Issues and Innovations |pages=257–274 |place=Cham |publisher=Springer |language=en |doi=10.1007/978-3-030-84729-6_18|isbn=978-3-030-84728-9 }}</ref> solving AI-complete problems would have strong repercussions on society.