AI-complete

related topics
{theory, work, human}
{math, number, function}
{system, computer, user}
{rate, high, increase}
{island, water, area}

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 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 algorithm.

AI-complete problems are hypothesised to include computer vision, natural language understanding, and dealing with unexpected circumstances while solving any real world problem.

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.[2][3]

Contents

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.[4] Early uses of the term are in Erik Mueller's 1987 Ph.D. dissertation[5] and in Eric Raymond's 1991 Jargon File.[6]

AI-complete problems

AI-complete problems are hypothesised to include:

Full article ▸

related documents
Bayesian probability
Nothing
Gottlob Frege
Incompatible-properties argument
Norm (sociology)
Sanity
Robert Nozick
The Blind Watchmaker
Non sequitur (logic)
Viruses of the Mind
Behavior
Arnold J. Toynbee
Artificial life
Deception
Hierarchical organization
Action theory
James P. Hogan (writer)
Social psychology
Ethnology
Social epistemology
Baconian method
John Ralston Saul
Four Temperaments
Daniel Dennett
Principle (disambiguation)
Integrity
Applied ethics
Ethnocentrism
Observation
The End of History and the Last Man