Полные задачи искусственного интеллекта: сложность и подходы к решению.

Term describing difficult problems in AI
In the field of artificial intelligence (AI), tasks that are hypothesised to require artificial general intelligence to solve are informally known as AI complete or AI hard. Calling a problem AI complete reflects the belief that it cannot 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. AI complete problems could be useful, for example, to test for the presence of humans as CAPTCHAs aim to do, and in computer security to circumvent brute force attacks.

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. Early uses of the term are in Erik Mueller's 1987 PhD dissertation and in Eric Raymond's 1991 Jargon File. Expert systems, that were popular in the 1980s, were able to solve very simple and/or restricted versions of AI complete problems, but never in their full generality. When AI researchers attempted to "scale up" their systems to handle more complicated, real world situations, the programs tended to become excessively brittle without commonsense knowledge or a rudimentary understanding of the situation: they would fail as unexpected circumstances outside of its original problem context would begin to appear. When human beings are dealing with new situations in the world, they are helped by their awareness of the general context: they know what the things around them are, why they are there, what they are likely to do and so on. They can recognize unusual situations and adjust accordingly. Expert systems lacked this adaptability and were brittle when facing new situations. DeepMind published a work in May 2022 in which they trained a single model to do several things at the same time. The model, named Gato, can "play Atari, caption images, chat, stack blocks with a real robot arm and much more, deciding based on its context whether to output text, joint torques, button presses, or other tokens." Similarly, some tasks once considered to be AI complete, like machine translation, are among the capabilities of large language models.

Computational complexity theory deals with the relative computational difficulty of computable functions. By definition, it does not cover problems whose solution is unknown or has not been characterised formally. Since many AI problems have no formalization yet, conventional complexity theory does not enable to formally define AI completeness. To address this problem, a complexity theory for AI has been proposed. It is based on a model of computation that splits the computational burden between a computer and a human: one part is solved by computer and the other part solved by human. This is formalised by a human assisted Turing machine. The formalisation defines algorithm complexity, problem complexity and reducibility which in turn allows equivalence classes to be defined. The complexity of executing an algorithm with a human assisted Turing machine is given by a pair , where the first element represents the complexity of the human's part and the second element is the complexity of the machine's part.