Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
AI-complete
open-in-new
<h2 id="history">History</h2> <p>The term was coined by <a href="/facts/Fanya_Montalvo/webbQdbR">Fanya Montalvo</a> by analogy with <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> and <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a> in <a href="/facts/Computational_complexity_theory/etHuVF3U">complexity theory</a>, which formally describes the most famous class of difficult problems.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> Early uses of the term are in Erik Mueller's 1987 PhD dissertation<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> and in <a href="/facts/Eric_S._Raymond/9jLGSUtk">Eric Raymond</a>'s 1991 <a href="/facts/Jargon_File/tt0EIKfV">Jargon File</a>.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p><p><a href="/facts/Expert_system/CUCzSEaX">Expert systems</a>, 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 <a href="/facts/Software_brittleness/w3sfqkvz">brittle</a> without <a href="/facts/Commonsense_knowledge/2pyWM2X6">commonsense knowledge</a> 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 <a href="/facts/Software_brittleness/w3sfqkvz">brittle</a> when facing new situations.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p><p><a href="/facts/DeepMind/n5ehBwCx">DeepMind</a> published a work in May 2022 in which they trained a single model to do several things at the same time. The model, named <a href="/facts/Gato_(DeepMind)/TWxE0x0o">Gato</a>, 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."<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> Similarly, some tasks once considered to be AI-complete, like <a href="/facts/Machine_translation/DGF3NwuI">machine translation</a>,<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> are among the capabilities of <a href="/facts/Large_language_model/WnogWVJY">large language models</a>.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> </p> <h2 id="ai-complete-problems">AI-complete problems</h2> <p>AI-complete problems have been hypothesized to include: </p> <ul><li>AI <a href="/facts/Peer_review/ly6yEgcW">peer review</a><a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> (composite <a href="/facts/Natural-language_understanding/5waCJC1e">natural language understanding</a>, <a href="/facts/Automated_reasoning/x5EdkKoU">automated reasoning</a>, <a href="/facts/Automated_theorem_proving/vKGvuKFI">automated theorem proving</a>, <a href="/facts/Formalism_(philosophy_of_mathematics)/g0690AVL">formalized</a> <a href="/facts/Logic/8JnpJLtt">logic</a> <a href="/facts/Expert_system/CUCzSEaX">expert system</a>)</li> <li><a href="/facts/Bongard_problem/UsHY5JkU">Bongard problems</a><a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a></li> <li><a href="/facts/Computer_vision/Tl2Yyk66">Computer vision</a> (and subproblems such as <a href="/facts/Object_recognition/cdLpak1I">object recognition</a>)<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a></li> <li><a href="/facts/Natural-language_understanding/5waCJC1e">Natural language understanding</a> (and subproblems such as <a href="/facts/Text_mining/5QsIa3Cz">text mining</a>,<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> <a href="/facts/Machine_translation/DGF3NwuI">machine translation</a>,<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> and <a href="/facts/Word-sense_disambiguation/Mfcw7gsu">word-sense disambiguation</a><a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a>)</li> <li><a href="/facts/Autonomous_driving/KXeFywXS">Autonomous driving</a><a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a></li> <li>Dealing with unexpected circumstances while solving any real world problem,<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a> whether <a href="/facts/Robotic_mapping/W9jnGGKe">navigation</a>, <a href="/facts/Automated_planning_and_scheduling/VL1TcrmD">planning</a>, or even the kind of <a href="/facts/Reasoning/tcBImN8J">reasoning</a> done by <a href="/facts/Expert_system/CUCzSEaX">expert systems</a>.</li></ul> <h2 id="formalization">Formalization</h2> <p><a href="/facts/Computational_complexity_theory/etHuVF3U">Computational complexity theory</a> deals with the relative computational difficulty of <a href="/facts/Computable_function/dzwBlLGn">computable functions</a>. 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. </p> <h2 id="research">Research</h2> <p><a href="/facts/Roman_Yampolskiy/9qNNaKAz">Roman Yampolskiy</a><a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a> suggests that a problem C {\displaystyle C} is AI-Complete if it has two properties: </p> <ul><li>It is in the set of AI problems (Human Oracle-solvable).</li> <li>Any AI problem can be converted into C {\displaystyle C} by some polynomial time algorithm.</li></ul> <p>On the other hand, a problem H {\displaystyle H} is AI-Hard if and only if there is an AI-Complete problem C {\displaystyle C} that is polynomial time Turing-reducible to H {\displaystyle H} . 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. </p><p>Yampolskiy<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a> has also hypothesized that the <a href="/facts/Turing_Test/wEvf9DIr">Turing Test</a> is a defining feature of AI-completeness. </p><p>Groppe and Jain<a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a> classify problems which require <a href="/facts/Artificial_general_intelligence/vbxwaq8t">artificial general intelligence</a> 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,<a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a> 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 <a href="/facts/Computational_complexity/Qenh22Ja">computational complexity</a> research being the limiting factor towards achieving artificial general intelligence. </p><p>For Kwee-Bintoro and Velez,<a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a> solving AI-complete problems would have strong repercussions on society. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/ASR-complete/hJPEpsFS">ASR-complete</a></li> <li><a href="/facts/List_of_unsolved_problems_in_computer_science/QySnBJ5E">List of unsolved problems in computer science</a></li> <li><a href="/facts/Synthetic_intelligence/kkkmL58I">Synthetic intelligence</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Shapiro, Stuart C. (1992). Artificial Intelligence Archived 2016-02-01 at the Wayback Machine In Stuart C. Shapiro (Ed.), Encyclopedia of Artificial Intelligence (Second Edition, pp. 54–57). New York: John Wiley. (Section 4 is on "AI-Complete Tasks".) <a href="http://www.cse.buffalo.edu/~shapiro/Papers/ai.pdf" target="_blank">http://www.cse.buffalo.edu/~shapiro/Papers/ai.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Yampolskiy, Roman (January 2013). "Turing Test as a Defining Feature of AI-Completeness" (PDF). Artificial Intelligence, Evolutionary Computing and Metaheuristics. Archived from the original (PDF) on 2013-05-22. <a href="https://web.archive.org/web/20130522094547/http://cecs.louisville.edu/ry/TuringTestasaDefiningFeature04270003.pdf" target="_blank">https://web.archive.org/web/20130522094547/http://cecs.louisville.edu/ry/TuringTestasaDefiningFeature04270003.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Luis von Ahn, Manuel Blum, Nicholas Hopper, and John Langford. CAPTCHA: Using Hard AI Problems for Security Archived 2016-03-04 at the Wayback Machine. In Proceedings of Eurocrypt, Vol. 2656 (2003), pp. 294–311. <a href="http://www.captcha.net/captcha_crypt.pdf" target="_blank">http://www.captcha.net/captcha_crypt.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Bergmair, Richard (January 7, 2006). "Natural Language Steganography and an "AI-complete" Security Primitive". CiteSeerX 10.1.1.105.129. {{cite journal}}: Cite journal requires |journal= (help) (unpublished?) <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Mallery, John C. (1988), "Thinking About Foreign Policy: Finding an Appropriate Role for Artificially Intelligent Computers", The 1988 Annual Meeting of the International Studies Association., St. Louis, MO, archived from the original on 2008-02-29, retrieved 2007-04-27{{citation}}: CS1 maint: location missing publisher (link). <a href="http://citeseer.ist.psu.edu/mallery88thinking.html" target="_blank">http://citeseer.ist.psu.edu/mallery88thinking.html</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Mueller, Erik T. (1987, March). Daydreaming and Computation (Technical Report CSD-870017) Archived 2020-10-30 at the Wayback Machine 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. 302) <a href="http://ftp.cs.ucla.edu/tech-report/198_-reports/870017.pdf" target="_blank">http://ftp.cs.ucla.edu/tech-report/198_-reports/870017.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Raymond, Eric S. (1991, March 22). Jargon File Version 2.8.1 Archived 2011-06-04 at the Wayback Machine (Definition of "AI-complete" first added to jargon file.) <a href="http://catb.org/esr/jargon/oldversions/jarg282.txt" target="_blank">http://catb.org/esr/jargon/oldversions/jarg282.txt</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Lenat, Douglas; Guha, R. V. (1989), Building Large Knowledge-Based Systems, Addison-Wesley, pp. 1–5 <a href="/wiki/Douglas_Lenat" target="_blank">/wiki/Douglas_Lenat</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>"A Generalist Agent". www.deepmind.com. Archived from the original on 2022-08-02. Retrieved 2022-05-26. <a href="https://www.deepmind.com/publications/a-generalist-agent" target="_blank">https://www.deepmind.com/publications/a-generalist-agent</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Katz, Miranda. "Welcome to the Era of the AI Coworker | Backchannel". Wired. ISSN 1059-1028. Retrieved 2024-04-28. <a href="https://www.wired.com/story/welcome-to-the-era-of-the-ai-coworker/" target="_blank">https://www.wired.com/story/welcome-to-the-era-of-the-ai-coworker/</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>"Unveiling the Power of Large Language Models (LLMs)". www.unite.ai. Retrieved 2024-04-28. <a href="https://www.unite.ai/large-language-models/" target="_blank">https://www.unite.ai/large-language-models/</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Stockton, Nick. "If AI Can Fix Peer Review in Science, AI Can Do Anything". Wired. ISSN 1059-1028. Retrieved 2024-04-27. <a href="https://www.wired.com/2017/02/ai-can-solve-peer-review-ai-can-solve-anything/" target="_blank">https://www.wired.com/2017/02/ai-can-solve-peer-review-ai-can-solve-anything/</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Šekrst, Kristina (2020), Skansi, Sandro (ed.), "AI-Completeness: Using Deep Learning to Eliminate the Human Factor", Guide to Deep Learning Basics: Logical, Historical and Philosophical Perspectives, Cham: Springer International Publishing, pp. 117–130, doi:10.1007/978-3-030-37591-1_11, ISBN 978-3-030-37591-1, retrieved 2024-04-05 <a href="978-3-030-37591-1" target="_blank">978-3-030-37591-1</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Strat, Thomas M.; Chellappa, Rama; Patel, Vishal M. (2020). "Vision and robotics". AI Magazine. 42 (2): 49–65. doi:10.1609/aimag.v41i2.5299. S2CID 220687545 – via ABI/INFORM Collection. <a href="https://doi.org/10.1609%2Faimag.v41i2.5299" target="_blank">https://doi.org/10.1609%2Faimag.v41i2.5299</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Krestel, Ralf; Aras, Hidir; Andersson, Linda; Piroi, Florina; Hanbury, Allan; Alderucci, Dean (2022-07-06). "3rd Workshop on Patent Text Mining and Semantic Technologies (PatentSemTech2022)". Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. Madrid Spain: ACM. pp. 3474–3477. doi:10.1145/3477495.3531702. ISBN 978-1-4503-8732-3. S2CID 250340282. Archived from the original on 2023-04-15. Retrieved 2023-04-15. <a href="978-1-4503-8732-3" target="_blank">978-1-4503-8732-3</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Orynycz, Petro (2022), Degen, Helmut; Ntoa, Stavroula (eds.), "Say It Right: AI Neural Machine Translation Empowers New Speakers to Revitalize Lemko", Artificial Intelligence in HCI, Lecture Notes in Computer Science, vol. 13336, Cham: Springer International Publishing, pp. 567–580, doi:10.1007/978-3-031-05643-7_37, ISBN 978-3-031-05642-0, retrieved 2023-04-15 <a href="978-3-031-05642-0" target="_blank">978-3-031-05642-0</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Ide, N.; Veronis, J. (1998). "Introduction to the special issue on word sense disambiguation: the state of the art" (PDF). Computational Linguistics. 24 (1): 2–40. Archived (PDF) from the original on 2022-10-09. <a href="https://www.aclweb.org/anthology/J/J98/J98-1001.pdf" target="_blank">https://www.aclweb.org/anthology/J/J98/J98-1001.pdf</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Musk, Elon (April 14, 2022). "Elon Musk talks Twitter, Tesla and how his brain works — live at TED2022". TED (conference) (Interview). Interviewed by Chris_Anderson_(entrepreneur). Vancouver. Archived from the original on December 15, 2022. Retrieved December 15, 2022. <a href="/wiki/Elon_Musk" target="_blank">/wiki/Elon_Musk</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>Šekrst, Kristina (2020), "Chapter 11 - AI-Completeness: Using Deep Learning to Eliminate the Human Factor", in Skansi, Sandro (ed.), Guide to Deep Learning Basics, Springer, ISBN 978-3-030-37591-1 <a href="978-3-030-37591-1" target="_blank">978-3-030-37591-1</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>Yampolskiy, Roman (2012), "AI-Complete, AI-Hard, or AI-Easy – Classification of Problems in AI" (PDF), 23rd Midwest Artificial Intelligence and Cognitive Science Conference, MAICS 2012, Cincinnati, Ohio, USA, 21-22 April 2012, retrieved 2024-04-05 <a href="https://www.proceedings.com/content/022/022437webtoc.pdf" target="_blank">https://www.proceedings.com/content/022/022437webtoc.pdf</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>Yampolskiy, Roman (2013), "Turing Test as a Defining Feature of AI-Completeness", Artificial Intelligence, Evolutionary Computing and Metaheuristics, Studies in Computational Intelligence, vol. 427, pp. 3–17, doi:10.1007/978-3-642-29694-9_1, ISBN 978-3-642-29693-2 <a href="978-3-642-29693-2" target="_blank">978-3-642-29693-2</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>Groppe, Sven; Jain, Sarika (2024), "The Way Forward with AI-Complete Problems", New Generation Computing, 42: 1–5, doi:10.1007/s00354-024-00251-8 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>Šekrst, Kristina (2020), Skansi, Sandro (ed.), "AI-Completeness: Using Deep Learning to Eliminate the Human Factor", Guide to Deep Learning Basics: Logical, Historical and Philosophical Perspectives, Cham: Springer International Publishing, pp. 117–130, doi:10.1007/978-3-030-37591-1_11, ISBN 978-3-030-37591-1, retrieved 2024-04-05 <a href="978-3-030-37591-1" target="_blank">978-3-030-37591-1</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>Kwee-Bintoro, Ted; Velez, Noah (2022), "AI-Complete: What it Means to Be Human in an Increasingly Computerized World", Bridging Human Intelligence and Artificial Intelligence, Educational Communications and Technology: Issues and Innovations, Cham: Springer, pp. 257–274, doi:10.1007/978-3-030-84729-6_18, ISBN 978-3-030-84728-9 <a href="978-3-030-84728-9" target="_blank">978-3-030-84728-9</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> </ol>