AI-complete: Difference between revisions
Jump to navigation
Jump to search
imported>Citation bot Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Computational problems | #UCB_Category 13/31 |
imported>Alenoach Removed a preprint source, rephrased the sentence |
||
| Line 2: | Line 2: | ||
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. 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 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. 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. | ||
Prior to 2013, 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 book |last=Yampolskiy |first=Roman |chapter=Turing Test as a Defining Feature of AI-Completeness |date=January 2013 |title=Artificial Intelligence, Evolutionary Computing and Metaheuristics |chapter-url=http://cecs.louisville.edu/ry/TuringTestasaDefiningFeature04270003.pdf |series=Studies in Computational Intelligence |volume=427 |pages=3–17 |doi=10.1007/978-3-642-29694-9_1 |isbn=978-3-642-29693-2 |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 distinguishing humans from automated agents, as [[CAPTCHA]]s aim to do.<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> | |||
==History== | ==History== | ||