Editing AI-complete (section)

{{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>