AI-Complete Problem
Definition
An AI-complete problem is an informal term for tasks that presumably require general AI capabilities.
The term is not a formal complexity class like NP-complete. It was historically used for tasks whose complete solution would require broad world knowledge, language understanding, or general problem solving.
Simply explained
Like a task that requires not just a special trick but many human abilities simultaneously.
Why it matters in practice
More relevant for classifying AI boundaries and term history than as a practical project category.
Example from business
A team avoids claiming that a single benchmark proves the solution of an "AI-complete" problem.
Limits and pitfalls
- Treat the term mathematically like NP-complete; equate today's partial successes with complete general intelligence.
Origin & history
Stuart C. Shapiro described "AI-Complete Tasks" in 1992 in the Encyclopedia of Artificial Intelligence; the term remained informal.
Use in mid-sized companies
- Possible application in SMEs: Distinguish between narrowly limited automation tasks and very general problem requirements in strategy discussions.
Frequently asked questions
Is AI-complete formally proven?
No. Is the term a standard benchmark today? No.
Sources
Shapiro, S. C. (1992), “Artificial Intelligence”, Encyclopedia of Artificial Intelligence, 2nd ed., Wiley, section "AI-Complete Tasks" Sources checked on 10.10.2026.
Editorially reviewed on: