AI-Complete Task
(Redirected from AI-Complete)
Jump to navigation
Jump to search
An AI-Complete Task is an AI task that requires artificial general intelligence capability.
- …
- Example(s):
- Counter-Example(s):
- See: Computer Vision, Human Computation.
References
2014
- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/AI-complete Retrieved:2014-4-3.
- In the field of artificial intelligence, the most difficult problems are informally known as AI-complete or AI-hard, implying that the difficulty of these computational problems is equivalent to that of solving the central artificial intelligence problem — making computers as intelligent as people, or strong AI.[1] To call a problem AI-complete reflects an attitude that it would not be solved by a simple specific algorithm.
AI-complete problems are hypothesised to include computer vision, natural language understanding, and dealing with unexpected circumstances while solving any real world problem. [2] With current technology, AI-complete problems cannot be solved by computer alone, but also require human computation. This property can be useful, for instance to test for the presence of humans as with CAPTCHAs, and for computer security to circumvent brute-force attacks. [3] [4]
- In the field of artificial intelligence, the most difficult problems are informally known as AI-complete or AI-hard, implying that the difficulty of these computational problems is equivalent to that of solving the central artificial intelligence problem — making computers as intelligent as people, or strong AI.[1] To call a problem AI-complete reflects an attitude that it would not be solved by a simple specific algorithm.
- ↑ Shapiro, Stuart C. (1992). Artificial Intelligence 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".)
- ↑ Roman V. Yampolskiy. Turing Test as a Defining Feature of AI-Completeness . In Artificial Intelligence, Evolutionary Computation and Metaheuristics (AIECM) --In the footsteps of Alan Turing. Xin-She Yang (Ed.). pp. 3-17. (Chapter 1). Springer, London. 2013. http://cecs.louisville.edu/ry/TuringTestasaDefiningFeature04270003.pdf
- ↑ Luis von Ahn, Manuel Blum, Nicholas Hopper, and John Langford. CAPTCHA: Using Hard AI Problems for Security. In: Proceedings of Eurocrypt, Vol. 2656 (2003), pp. 294-311.
- ↑ | date = January 7, 2006 }} (unpublished?)
2013
- (Waltinger et al., 2013) ⇒ Ulli Waltinger, Dan Tecuci, Mihaela Olteanu, Vlad Mocanu, and Sean Sullivan. (2013). “USI Answers: Natural Language Question Answering Over (Semi-) Structured Industry Data.” In: Twenty-Fifth IAAI Conference.
- QUOTE: Natural Language Understanding (NLU) has long been a goal of AI. Considered an AI-complete task, it consists of mapping natural language sentence into a complete, unambiguous, formal meaning representation expressed in a formal language which supports other tasks such as automated reasoning, or question answering.
2009
- (Navigli, 2009) ⇒ Roberto Navigli. (2009). “Word Sense Disambiguation: A Survey.” In: ACM Computing Surveys (CSUR) Journal, 41(2). doi:10.1145/1459352.1459355
- QUOTE: Word sense disambiguation (WSD) is the ability to identify the meaning of words in context in a computational manner. WSD is considered an AI-complete problem, that is, a task whose solution is at least as hard as the most difficult problems in artificial intelligence.
1998
- (Nancy & Véronis, 1998) ⇒ Nancy Ide, and Jean Véronis. "Introduction to the special issue on word sense disambiguation: the state of the art.” In: Computational Linguistics, 24(1).
- QUOTE: The problem of word sense disambiguation (WSD) has been described as “AI-complete," that is, a problem which can be solved only by first resolving all the difficult problems in artificial intelligence (AI), such as the representation of common sense and encyclopedic knowledge. The inherent difficulty of sense disambiguation was a central point in Bar-Hillel's well-known treatise on machine translation (Bar-Hillel 1960), where he asserted that he saw no means by which the sense of the word pen in the sentence The box is in the pen could be determined automatically.