From the JargonFile: 

Used to describe problems or subproblems in AI, to indicate that the solution presupposes a solution to the `strong AI problem' (that is, the synthesis of a human-level intelligence). A problem that is AI-complete is, in other words, just too hard. 

The name is intended to be a pun on NP-Completeness from ComplexityTheory.

----
I (DennisGorelik) think that this problem is not very hard.
Welcome to AisDevelopment. Take part in the future.

There is some strong mathematics around NP-Completeness, where-by problems are transformed into each other (in polynomial time) to prove their equivalence. I doubt there is anything so formal about AI-Completeness, but intuitively I expect all AI-Complete problems will have some common kernel. It will probably involve answering the question, "When are two things the same?"

[Presumably answering this question would be in itself an AiComplete problem?]
----
And once again I (DennisGorelik) think this question is not very hard.

''Then answer it.''
----
In its general form this question is almost certainly in the same category as the famous Turing "Halting Problem".  Consider, for example, two systems that use true random variables as part of their internal controls, but are otherwise "identical". How does one demonstrate that the systems are indeed identical when even if their inputs are identical the processing is based in probability and the outputs are always different, albeit correlated using statistics theory?

Consider, as another example, proving that two radically different algorithms for computing PI generate identical output. One cannot simply compare the two algorithms to prove identity because they use wildly distinct approaches, nor can one compare the outputs because PI is irrational. One would be forced to invoke some "higher knowledge" to show that mathematically the algorithms both compute PI. This is very similar to the "Oracle" that provides an answer which you can then test for correctness in NP complexity theory. Note that there are some algorithms used even today that are believed to accurately compute PI, but have never been "proven" to do so.

Yes, in simple (and even some fairly complex) cases this question is easy to answer, just as in simple and even some fairly complex cases we can precisely answer the halting problem. (KarlCHansen)

----
See also NpComplete