Editing AI-complete

{{Short description|Term describing difficult problems in AI}}
In the field of [[artificial intelligence]] (AI), tasks that are hypothesized to require [[artificial general intelligence]] to solve are informally known as '''AI-complete''' or '''AI-hard'''.<ref name=" Shapiro92">Shapiro, Stuart C. (1992). [http://www.cse.buffalo.edu/~shapiro/Papers/ai.pdf Artificial Intelligence] {{Webarchive|url=https://web.archive.org/web/20160201014644/http://www.cse.buffalo.edu/~shapiro/Papers/ai.pdf |date=2016-02-01 }} In Stuart C. Shapiro (Ed.), ''Encyclopedia of Artificial Intelligence'' (Second Edition, pp.&nbsp;54–57). New York: John Wiley. (Section 4 is on "AI-Complete Tasks".)</ref> Calling a problem AI-complete reflects the belief that it cannot be solved by a simple specific algorithm.  

In the past, problems supposed to be AI-complete included [[computer vision]], [[natural-language understanding|natural language understanding]], and dealing with unexpected circumstances while solving any real-world problem.<ref>{{Cite journal |last=Yampolskiy |first=Roman |date=January 2013 |title=Turing Test as a Defining Feature of AI-Completeness |url=http://cecs.louisville.edu/ry/TuringTestasaDefiningFeature04270003.pdf |journal=Artificial Intelligence, Evolutionary Computing and Metaheuristics |archive-url=https://web.archive.org/web/20130522094547/http://cecs.louisville.edu/ry/TuringTestasaDefiningFeature04270003.pdf |archive-date=2013-05-22}}</ref> AI-complete tasks were notably considered useful for testing the presence of humans, as [[CAPTCHA]]s aim to do, and in [[computer security]] to circumvent [[brute-force attack]]s.<ref>Luis von Ahn, Manuel Blum, Nicholas Hopper, and John Langford. [http://www.captcha.net/captcha_crypt.pdf CAPTCHA: Using Hard AI Problems for Security] {{Webarchive|url=https://web.archive.org/web/20160304001102/http://www.captcha.net/captcha_crypt.pdf |date=2016-03-04 }}. In Proceedings of Eurocrypt, Vol. 2656 (2003), pp. 294–311.</ref><ref>{{cite journal | first = Richard | last = Bergmair | title = Natural Language Steganography and an "AI-complete" Security Primitive | citeseerx = 10.1.1.105.129 | date = January 7, 2006 }} (unpublished?)</ref>

==History==
The term was coined by [[Fanya Montalvo]] by analogy with [[NP-complete]] and [[NP-hard]] in [[Computational complexity theory|complexity theory]], which formally describes the most famous class of difficult problems.<ref>{{Citation | last=Mallery | first=John C. | year=1988 | url=http://citeseer.ist.psu.edu/mallery88thinking.html | contribution=Thinking About Foreign Policy: Finding an Appropriate Role for Artificially Intelligent Computers | title=The 1988 Annual Meeting of the International Studies Association. | location=St. Louis, MO | access-date=2007-04-27 | archive-date=2008-02-29 | archive-url=https://web.archive.org/web/20080229024012/http://citeseer.ist.psu.edu/mallery88thinking.html | url-status=live }}.</ref> Early uses of the term are in Erik Mueller's 1987 PhD dissertation<ref>Mueller, Erik T. (1987, March). [http://ftp.cs.ucla.edu/tech-report/198_-reports/870017.pdf ''Daydreaming and Computation'' (Technical Report CSD-870017)] {{Webarchive|url=https://web.archive.org/web/20201030213109/http://ftp.cs.ucla.edu/tech-report/198_-reports/870017.pdf |date=2020-10-30 }} PhD dissertation, University of California, Los Angeles. ("Daydreaming is but one more ''AI-complete'' problem: if we could solve anyone artificial intelligence problem, we could solve all the others", p.&nbsp;302)</ref> and in [[Eric S. Raymond|Eric Raymond]]'s 1991 [[Jargon File]].<ref>Raymond, Eric S. (1991, March 22). [http://catb.org/esr/jargon/oldversions/jarg282.txt Jargon File Version 2.8.1] {{Webarchive|url=https://web.archive.org/web/20110604150347/http://catb.org/esr/jargon/oldversions/jarg282.txt |date=2011-06-04 }} (Definition of "AI-complete" first added to jargon file.)</ref>

[[Expert system]]s, that were popular in the 1980s, were able to solve very simple and/or restricted versions of AI-complete problems, but never in their full generality. When AI researchers attempted to "scale up" their systems to handle more complicated, real-world situations, the programs tended to become excessively [[Software brittleness|brittle]] without [[commonsense knowledge]] or a rudimentary understanding of the situation: they would fail as unexpected circumstances outside of its original problem context would begin to appear. When human beings are dealing with new situations in the world, they are helped by their awareness of the general context: they know what the things around them are, why they are there, what they are likely to do and so on. They can recognize unusual situations and adjust accordingly. Expert systems lacked this adaptability and were [[Software brittleness|brittle]] when facing new situations.<ref>{{Citation |last1=Lenat |first1=Douglas |title=Building Large Knowledge-Based Systems |pages=1–5 |year=1989 |publisher=Addison-Wesley |last2=Guha |first2=R. V. |author-link=Douglas Lenat}}</ref>

[[DeepMind]] published a work in May 2022 in which they trained a single model to do several things at the same time. The model, named [[Gato (DeepMind)|Gato]], can "play Atari, caption images, chat, stack blocks with a real robot arm and much more, deciding based on its context whether to output text, joint torques, button presses, or other tokens."<ref>{{Cite web |title=A Generalist Agent |url=https://www.deepmind.com/publications/a-generalist-agent |url-status=live |archive-url=https://web.archive.org/web/20220802000307/https://www.deepmind.com/publications/a-generalist-agent |archive-date=2022-08-02 |access-date=2022-05-26 |website=www.deepmind.com |language=en}}</ref> Similarly, some tasks once considered to be AI-complete, like [[machine translation]],<ref>{{Cite magazine |last=Katz |first=Miranda |title=Welcome to the Era of the AI Coworker {{!}} Backchannel |url=https://www.wired.com/story/welcome-to-the-era-of-the-ai-coworker/ |access-date=2024-04-28 |magazine=Wired |language=en-US |issn=1059-1028}}</ref> are among the capabilities of [[large language model]]s.<ref>{{Cite web |title=Unveiling the Power of Large Language Models (LLMs) |url=https://www.unite.ai/large-language-models/ |access-date=2024-04-28 |website=www.unite.ai}}</ref>

==AI-complete problems==
AI-complete problems have been hypothesized to include:

* AI [[peer review]]<ref>{{Cite magazine |last=Stockton |first=Nick |title=If AI Can Fix Peer Review in Science, AI Can Do Anything |url=https://www.wired.com/2017/02/ai-can-solve-peer-review-ai-can-solve-anything/ |access-date=2024-04-27 |magazine=Wired |language=en-US |issn=1059-1028}}</ref> (composite [[natural-language understanding|natural language understanding]], [[automated reasoning]], [[automated theorem proving]], [[Formalism (philosophy of mathematics)|formalized]] [[logic]] [[expert system]])
* [[Bongard problem]]s<ref name="Sekrst2020">{{Citation |last=Šekrst |first=Kristina |title=AI-Completeness: Using Deep Learning to Eliminate the Human Factor |date=2020 |work=Guide to Deep Learning Basics: Logical, Historical and Philosophical Perspectives |pages=117–130 |editor-last=Skansi |editor-first=Sandro |url=https://doi.org/10.1007/978-3-030-37591-1_11 |access-date=2024-04-05 |place=Cham |publisher=Springer International Publishing |language=en |doi=10.1007/978-3-030-37591-1_11 |isbn=978-3-030-37591-1|url-access=subscription }}</ref>
* [[Computer vision]] (and subproblems such as [[object recognition]])<ref>{{Cite journal |last1=Strat |first1=Thomas M. |last2=Chellappa |first2=Rama |last3=Patel |first3=Vishal M. |date=2020 |title=Vision and robotics |journal=AI Magazine |volume=42 |issue=2 |pages=49–65 |doi=10.1609/aimag.v41i2.5299 |s2cid=220687545 |via=ABI/INFORM Collection|doi-access=free }}</ref>
* [[Natural-language understanding|Natural language understanding]] (and subproblems such as [[text mining]],<ref>{{Cite book |last1=Krestel |first1=Ralf |last2=Aras |first2=Hidir |last3=Andersson |first3=Linda |last4=Piroi |first4=Florina |last5=Hanbury |first5=Allan |last6=Alderucci |first6=Dean |title=Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval |chapter=3rd Workshop on Patent Text Mining and Semantic Technologies (PatentSemTech2022) |date=2022-07-06 |chapter-url=https://dl.acm.org/doi/10.1145/3477495.3531702 |language=en |location=Madrid Spain |publisher=ACM |pages=3474–3477 |doi=10.1145/3477495.3531702 |isbn=978-1-4503-8732-3 |s2cid=250340282 |access-date=2023-04-15 |archive-date=2023-04-15 |archive-url=https://web.archive.org/web/20230415213932/https://dl.acm.org/doi/10.1145/3477495.3531702 |url-status=live }}</ref> [[machine translation]],<ref>{{Citation |last=Orynycz |first=Petro |title=Say It Right: AI Neural Machine Translation Empowers New Speakers to Revitalize Lemko |date=2022 |url=https://link.springer.com/10.1007/978-3-031-05643-7_37 |work=Artificial Intelligence in HCI |series=Lecture Notes in Computer Science |volume=13336 |pages=567–580 |editor-last=Degen |editor-first=Helmut |access-date=2023-04-15 |place=Cham |publisher=Springer International Publishing |language=en |doi=10.1007/978-3-031-05643-7_37 |isbn=978-3-031-05642-0 |editor2-last=Ntoa |editor2-first=Stavroula|url-access=subscription }}</ref> and [[word-sense disambiguation]]<ref>{{Cite journal |last1=Ide |first1=N. |last2=Veronis |first2=J. |year=1998 |title=Introduction to the special issue on word sense disambiguation: the state of the art |journal=Computational Linguistics |volume=24 |issue=1 |pages=2–40|url=https://www.aclweb.org/anthology/J/J98/J98-1001.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.aclweb.org/anthology/J/J98/J98-1001.pdf |archive-date=2022-10-09 |url-status=live}}</ref>)
* [[Autonomous driving]]<ref>{{cite interview |last=Musk |first=Elon |subject-link=Elon Musk |interviewer=[[Chris_Anderson_(entrepreneur)]] |title=Elon Musk talks Twitter, Tesla and how his brain works — live at TED2022 |work=[[TED (conference)]] |location=Vancouver |date=April 14, 2022 |url=https://www.youtube.com/watch?v=cdZZpaB2kDM |access-date=December 15, 2022 |archive-date=December 15, 2022 |archive-url=https://web.archive.org/web/20221215004220/https://www.youtube.com/watch?v=cdZZpaB2kDM |url-status=live }}</ref>
* Dealing with unexpected circumstances while solving any real world problem,<ref>{{Citation |last=Šekrst |first=Kristina |title=Guide to Deep Learning Basics |date=2020 |work= |editor-last=Skansi |editor-first=Sandro |url=https://philarchive.org/archive/EKRAUD |chapter=Chapter 11 - AI-Completeness: Using Deep Learning to Eliminate the Human Factor |publisher=Springer |language=en |isbn=978-3-030-37591-1}}</ref> whether [[robotic mapping|navigation]], [[automated planning and scheduling|planning]], or even the kind of [[reasoning]] done by [[expert system]]s.{{citation needed|date=February 2021}}

==Formalization==
[[Computational complexity theory]] deals with the relative computational difficulty of [[computable function]]s. By definition, it does not cover problems whose solution is unknown or has not been characterized formally. Since many AI problems have no formalization yet, conventional complexity theory does not enable a formal definition of AI-completeness.

==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. 

==See also==
* [[ASR-complete]]
* [[List of unsolved problems in computer science]]
* [[Synthetic intelligence]]

==References==
<references/>

{{Natural Language Processing}}

{{DEFAULTSORT:Ai-Complete}}
[[Category:Artificial intelligence]]
[[Category:Computational problems]]