AI-complete (also called AI-hard) is an informal label for problems whose full solution is believed to require general, human-level intelligence, so that solving any one of them would effectively solve the central problem of artificial intelligence. The term borrows its shape from NP-complete in computational complexity theory, but it describes a conjecture about cognitive difficulty rather than a formally proven class.
Within AI fundamentals, the label marks the boundary between tasks that narrow AI can master with enough data and engineering and tasks that seem to demand open-ended understanding of the world. Classic examples include unrestricted natural language understanding, fully general machine translation and robust commonsense reasoning.
Where the AI-complete idea comes from
The AI-complete concept arose from an analogy with complexity theory. In that field, a problem is NP-complete when every problem in the class NP can be reduced to it in polynomial time, so an efficient solution to one would solve them all. AI researchers in the 1980s and 1990s borrowed the structure to describe problems that seem to share a common core of difficulty: real understanding of meaning, context and the physical and social world.
The argument usually runs as an informal reduction. If a system could translate any text perfectly, it would have to resolve ambiguity, track references, infer intent and apply world knowledge, which are the same abilities needed for open conversation, story comprehension and planning. Because these abilities seem inseparable, solving one task completely would imply solving the rest.
Researchers have proposed more rigorous versions. One line of work defines an AI-complete class through human oracles, measuring how much a task relies on queries to a human-level solver. These proposals remain academic sketches; no accepted formal definition exists, and the term functions mainly as a shorthand for very hard problems.
Problems commonly called AI-complete
The canonical list of AI-complete problems centers on language, perception and reasoning in open settings. The table below summarizes the most cited candidates and the ability each is thought to require.
| Problem | Why it is considered AI-complete | Typical failure without general understanding |
|---|---|---|
| Natural language understanding | Meaning depends on context, intent and world knowledge | Misreads sarcasm, idioms or implied requests |
| Fully general machine translation | Translation needs disambiguation beyond surface statistics | Wrong pronoun gender or word sense in rare contexts |
| Commonsense reasoning | Requires vast implicit knowledge of everyday physics and society | Accepts physically impossible scenarios |
| Open-domain dialogue | Must track goals, beliefs and topic shifts indefinitely | Contradicts itself over long conversations |
| General computer vision | Scene meaning depends on function, causality and intent | Recognizes objects but misreads the situation |
| Autonomous action in open worlds | Requires planning under novelty and the frame problem | Breaks down on situations absent from training |
Researchers often add the Turing test itself, since passing an unrestricted version would require all of the abilities in the table. The Winograd Schema Challenge was designed in the same spirit: pronoun resolution that depends on commonsense knowledge rather than word statistics.
How AI-complete compares with related concepts
AI-complete is easily confused with formal complexity classes and with goals such as artificial general intelligence. The comparison below separates a claim about difficulty from a claim about a system.
| Concept | What it describes | Formal status |
|---|---|---|
| AI-complete | Problems needing human-level general intelligence | Informal conjecture |
| NP-complete | Hardest problems in the class NP under polynomial reductions | Rigorously defined and proven |
| Artificial general intelligence | A system that matches humans across most cognitive tasks | Contested definition, no agreed test |
| Narrow AI | A system built for one task or a limited domain | Descriptive category |
| Moravec’s paradox | Observation that perception and motor skills are harder for machines than abstract reasoning | Empirical observation |
The key distinction is that NP-completeness is a theorem-backed property, while AI-completeness is an intuition about shared cognitive prerequisites. Calling a problem AI-complete therefore expresses an expectation, not a proof, and that expectation can be revised when evidence changes.
How modern language models challenge the concept
Large language models have eroded several classic examples. Systems trained on massive text corpora now translate, summarize and answer questions at a level many researchers once considered impossible without general intelligence, yet most specialists do not regard these systems as fully general minds.
This outcome supports two competing readings. One holds that the original list was wrong: tasks believed to be AI-complete can be solved well enough through scale and statistical learning, consistent with the bitter lesson. The other holds that the tasks are still unsolved in their full, unrestricted form, since models still fail on adversarial inputs, rare contexts and long-horizon reasoning.
The table below shows how the status of several candidates has shifted in practice.
| Problem | Earlier view | Current practical status |
|---|---|---|
| Machine translation | Requires full understanding | High quality for common language pairs, weaker on low-resource languages |
| Winograd schemas | Benchmark for commonsense | Largely saturated by large models, with doubts about shortcut learning |
| Open-domain dialogue | Out of reach | Fluent but prone to hallucination and inconsistency |
| Robotic manipulation | Hard but narrower | Still limited in unstructured homes and workplaces |
Using the label responsibly
The AI-complete label is useful as a planning and expectation-setting tool. When a product requirement is AI-complete in its unrestricted form, teams should narrow the scope, add human review or accept a defined error rate rather than wait for a general solution.
| Unrestricted goal | Tractable restriction | Remaining risk |
|---|---|---|
| Understand any customer message | Classify messages into 20 known intents | Unusual requests misrouted |
| Translate any document perfectly | Translate with terminology glossaries and human post-editing | Subtle legal nuance |
| Answer any question correctly | Answer from a curated document set with citations | Gaps in the document set |
| Drive anywhere | Operate in a mapped, geofenced area | Rare edge cases |
- Do not treat the label as proof: it records a belief that can be wrong.
- Avoid moving the goalposts only after a task is solved; state the criteria in advance.
- Separate benchmark success from task mastery: a saturated benchmark does not show that the full problem is solved.
- Describe scope precisely when claiming that a system handles an AI-hard task.
Explained without jargon
Some problems look separate but secretly need the same thing: a real grasp of how the world works. Translating a joke, following a long conversation and understanding a messy photo all depend on knowing what people mean and what usually happens in everyday life.
Calling a problem AI-complete means it cannot be fully solved without that general understanding. It is like a master key: if a machine could truly do one of these tasks, it could probably do them all. The label is an educated guess, not a proven fact, and recent AI progress has shown that some of these guesses were too pessimistic.
A typical use case
A mid-sized insurance company plans a chatbot that should “understand any customer email and resolve it automatically”. During scoping, the lead engineer points out that the goal, stated that way, is an AI-complete requirement: unrestricted email understanding needs context, intent detection and knowledge of policies and human situations.
The team narrows the scope. The system classifies incoming emails into 18 defined request types, drafts replies only for the 6 most routine ones, and routes everything else to staff. After three months, it handles about 40 percent of volume automatically with an error rate the claims department accepts, and nobody expected it to match a human agent on unusual cases. Recognizing the AI-complete core early kept the project realistic and on budget.