AI-complete: Difference between revisions

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Next edit →
VisualWikitext
imported>OAbot
m Open access bot: url-access updated in citation with #oabot.
 
imported>OAbot
m Open access bot: doi updated in citation with #oabot.
Line 15: Line 15:


* 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]])
* 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>
* [[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 |doi-access=free }}</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>
* [[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>)
* [[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>)

Revision as of 04:29, 2 June 2025

Template:Short description 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.[1] 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, and dealing with unexpected circumstances while solving any real-world problem.[2] AI-complete tasks were notably considered useful for testing the presence of humans, as CAPTCHAs aim to do, and in computer security to circumvent brute-force attacks.[3][4]

History

The term was coined by Fanya Montalvo by analogy with NP-complete and NP-hard in complexity theory, which formally describes the most famous class of difficult problems.[5] Early uses of the term are in Erik Mueller's 1987 PhD dissertation[6] and in Eric Raymond's 1991 Jargon File.[7]

Expert systems, 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 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 brittle when facing new situations.[8]

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, 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."[9] Similarly, some tasks once considered to be AI-complete, like machine translation,[10] are among the capabilities of large language models.[11]

AI-complete problems

AI-complete problems have been hypothesized to include:

Formalization

Computational complexity theory deals with the relative computational difficulty of computable functions. 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[20] suggests that a problem C 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 C by some polynomial time algorithm.

On the other hand, a problem H is AI-Hard if and only if there is an AI-Complete problem C that is polynomial time Turing-reducible to 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.

Yampolskiy[21] has also hypothesized that the Turing Test is a defining feature of AI-completeness.

Groppe and Jain[22] 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,[13] 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,[23] solving AI-complete problems would have strong repercussions on society.

See also

References

  1. ↑ Shapiro, Stuart C. (1992). Artificial Intelligence Template:Webarchive 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".)
  2. ↑ Script error: No such module "Citation/CS1".
  3. ↑ Luis von Ahn, Manuel Blum, Nicholas Hopper, and John Langford. CAPTCHA: Using Hard AI Problems for Security Template:Webarchive. In Proceedings of Eurocrypt, Vol. 2656 (2003), pp. 294–311.
  4. ↑ Script error: No such module "Citation/CS1". (unpublished?)
  5. ↑ Script error: No such module "citation/CS1"..
  6. ↑ Mueller, Erik T. (1987, March). Daydreaming and Computation (Technical Report CSD-870017) Template:Webarchive 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)
  7. ↑ Raymond, Eric S. (1991, March 22). Jargon File Version 2.8.1 Template:Webarchive (Definition of "AI-complete" first added to jargon file.)
  8. ↑ Script error: No such module "citation/CS1".
  9. ↑ Script error: No such module "citation/CS1".
  10. ↑ Template:Cite magazine
  11. ↑ Script error: No such module "citation/CS1".
  12. ↑ Template:Cite magazine
  13. ↑ a b Script error: No such module "citation/CS1".
  14. ↑ Script error: No such module "Citation/CS1".
  15. ↑ Script error: No such module "citation/CS1".
  16. ↑ Script error: No such module "citation/CS1".
  17. ↑ Script error: No such module "Citation/CS1".
  18. ↑ Script error: No such module "citation/CS1".
  19. ↑ Script error: No such module "citation/CS1".
  20. ↑ Script error: No such module "citation/CS1".
  21. ↑ Script error: No such module "citation/CS1".
  22. ↑ Script error: No such module "citation/CS1".
  23. ↑ Script error: No such module "citation/CS1".

Template:Natural Language Processing

Retrieved from "http://debianws.lexgopc.com/wiki143/index.php?title=AI-complete&oldid=617965"