AI Hardness: Why Some AI Problems Are Solved Easily and Others Stay Expensive

An industrial SAT solver can handle formulas with millions of variables, even though SAT is NP-complete. A large language model can write fluent code, yet still get the product of two long numbers wrong. Both are called "hard problems", but they are hard in two entirely different senses.

This article is built around one question: why are some AI problems handled efficiently, while others still demand huge compute, high-quality data or entirely new methods?

What AI Hardness is, and what it is not

One caveat first: "AI Hardness" is not a term with a single standard definition. The closest established notions are "AI-hard" and "AI-complete", borrowed informally from NP-completeness to describe problems thought to be as hard as building general intelligence. They carry no formal proof the way NP-completeness does. In this article I use AI Hardness as an umbrella for four different layers of difficulty in building AI systems:

• Computational difficulty: the time and memory an algorithm needs as the problem grows.
• Training difficulty: the cost of finding good model parameters from data.
• Inference difficulty: whether a model returns correct, reliable answers on a specific problem.
• Evaluation difficulty: whether we can measure a model's real capability trustworthily.

Concept	Question it answers	Scope
Computational complexity	How many resources does the best algorithm need?	Theoretical, as a function of input size
NP-hardness	Is the problem at least as hard as every problem in NP?	Worst case, assuming P ≠ NP
Training difficulty	How much data and compute does a model need to converge well?	Empirical, depends on architecture and data
Inference complexity	What does running the model cost, and how accurate is multi-step reasoning?	Both theoretical and empirical
Evaluation difficulty	Does a score reflect real ability?	Measurement methodology

The key point: NP-hard does not mean "AI cannot solve it". NP-hardness describes the worst case. The travelling salesman problem (TSP) is NP-hard, yet the Concorde solver has found a provably optimal tour for an 85,900-city instance (Applegate et al., 2006). Approximation algorithms such as Christofides (1976) guarantee a tour within 1.5 times optimal for metric TSP. Conversely, a problem that is not NP-hard can still be very hard for a machine-learning model if data is scarce or evaluation is flawed.

A. Computational difficulty

The most familiar example is self-attention in the Transformer (Vaswani et al., 2017). For a sequence of length n, each layer builds an n × n matrix, so time and memory grow quadratically with context length. Doubling the context makes the attention step roughly four times more expensive.

The cause is the comparison of every token pair. Remedies include sparse or approximate attention, and FlashAttention (Dao et al., 2022), which still computes exact attention but reorganises GPU memory reads and writes so that memory grows linearly with sequence length. The remaining limit: the number of operations is still quadratic, and approximate methods can trade away quality.

B. Training difficulty

In theory, training can be genuinely hard: Blum and Rivest (1992) proved that training a 3-node neural network to fit a given dataset is NP-complete. Yet modern deep networks are not blocked by this result, because we do not demand a worst-case global minimum. Gradient descent is usually good enough, and some analyses (for example Choromanska et al., 2015) suggest that in large networks many local minima have similar quality, although that result concerns simplified models, not a general guarantee.

The practical difficulty lies in data, loss functions and resources. Zhang et al. (2017) showed that deep networks can fit even random labels, so fitting the training set does not guarantee generalisation. Kaplan et al. (2020) and Hoffmann et al. (2022, the Chinchilla model) found that loss falls as a power law when parameters, data and compute grow, and that for a fixed budget model size and training tokens must be balanced. These are empirical findings, not theorems. Cost can be reduced with parameter-efficient fine-tuning such as LoRA (Hu et al., 2021) and knowledge distillation (Hinton et al., 2015); the limit is that data quality cannot be replaced by more compute.

C. Inference difficulty

Dziri et al. (2023, "Faith and Fate") studied tasks that require composing many steps, such as multi-digit multiplication and dynamic programming, and reported that Transformer performance degrades quickly as complexity grows. On the theory side, Merrill and Sabharwal (2023) showed that log-precision Transformers fall in a shallow parallel circuit class (TC⁰), which limits what they can compute without many sequential steps. Feng et al. (2023) and related work show that generating intermediate steps (chain-of-thought) increases expressive power, which helps explain why chain-of-thought prompting (Wei et al., 2022) improves reasoning on many tasks.

For combinatorial problems and high-reliability requirements, the pragmatic approach is not to make the model compute everything itself: call tools or run code (Gao et al., 2022, PAL), sample several solutions and vote (Wang et al., 2022, self-consistency), or use the model as a heuristic for a classical solver. Some work uses machine learning to construct routing solutions (Kool et al., 2019), but there is no basis to claim these methods beat specialised solvers at every scale.

D. Evaluation difficulty

A high benchmark score does not mean the model has the corresponding capability. There are three main sources of error. First, data leakage: test data appears in training data, and Sainz et al. (2023) call for measuring contamination separately for each benchmark. Zhang et al. (2024) built GSM1k, a fresh benchmark resembling GSM8K, and observed notable score drops for some models, suggesting overfitting or contamination. Second, distribution shift: Recht et al. (2019) found that ImageNet classifiers lose clear accuracy on a newly rebuilt test set made with the same procedure. Third, the gap to real environments: SWE-bench (Jimenez et al., 2024) evaluates on real GitHub issues, closer to engineering work than short coding puzzles.

Remedies include keeping test sets private, refreshing benchmarks regularly, reporting evaluation conditions in full and, above all, testing on the data of the problem you actually plan to deploy. The limit: no benchmark covers every real-world situation.

E. Reducing difficulty: decompose and combine

These approaches share one logic: do not attack the general worst case head-on, narrow the practical problem instead. Concretely: change the algorithm or data structure to cut cost; pick a model that is just big enough rather than the largest (quantisation, distillation); decompose the problem into small, verifiable steps; combine learned models with exact solvers or tools; and improve data before adding parameters. The clearest example of the gap between theoretical and practical difficulty is protein folding: some theoretical models of it were proven NP-hard (Berger and Leighton, 1998), yet AlphaFold 2 (Jumper et al., 2021) reached high accuracy on many proteins at CASP14 by exploiting structure and data from real proteins, not by solving the worst case.

Conclusion and next steps

Five takeaways:

1. AI Hardness has no standard definition; state whether you mean computational, training, inference or evaluation difficulty.
2. NP-hard is a statement about the worst case, not a verdict on every specific instance.
3. Many current "limits" of AI are empirical (data, compute, architecture) and may change, unlike limits that have been proven.
4. Cost and reliability often improve more through decomposition and tool use than through scaling the model alone.
5. Benchmark scores are indirect evidence; evaluation on your own real data is the closest evidence you can get.

A step you can take today: pick one concrete problem from your own work, run both a classical heuristic and a machine-learning model on it, and compare quality, cost and stability on a test set that you keep private. If you read one of the papers below, check the evaluation conditions before looking at the numbers. Which kind of difficulty are you running into in your own project? Share it in the comments or get in touch.

References

Titles and authors below follow the original publications; please verify them on arXiv or the venue's page before citing.

• Vaswani et al. (2017). Attention Is All You Need. arXiv:1706.03762
• Dao et al. (2022). FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness. arXiv:2205.14135
• Blum & Rivest (1992). Training a 3-node neural network is NP-complete. Neural Networks 5(1).
• Choromanska et al. (2015). The Loss Surfaces of Multilayer Networks. arXiv:1412.0233
• Zhang et al. (2017). Understanding deep learning requires rethinking generalization. arXiv:1611.03530
• Kaplan et al. (2020). Scaling Laws for Neural Language Models. arXiv:2001.08361
• Hoffmann et al. (2022). Training Compute-Optimal Large Language Models. arXiv:2203.15556
• Hu et al. (2021). LoRA: Low-Rank Adaptation of Large Language Models. arXiv:2106.09685
• Hinton et al. (2015). Distilling the Knowledge in a Neural Network. arXiv:1503.02531
• Dziri et al. (2023). Faith and Fate: Limits of Transformers on Compositionality. arXiv:2305.18654
• Merrill & Sabharwal (2023). The Parallelism Tradeoff: Limitations of Log-Precision Transformers. arXiv:2207.00729
• Feng et al. (2023). Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective. arXiv:2305.15408
• Wei et al. (2022). Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. arXiv:2201.11903
• Wang et al. (2022). Self-Consistency Improves Chain of Thought Reasoning in Language Models. arXiv:2203.11171
• Gao et al. (2022). PAL: Program-aided Language Models. arXiv:2211.10435
• Kool, van Hoof & Welling (2019). Attention, Learn to Solve Routing Problems! arXiv:1803.08475
• Sainz et al. (2023). NLP Evaluation in trouble: On the Need to Measure LLM Data Contamination for each Benchmark. arXiv:2310.18018
• Zhang et al. (2024). A Careful Examination of Large Language Model Performance on Grade School Arithmetic. arXiv:2405.00332
• Recht et al. (2019). Do ImageNet Classifiers Generalize to ImageNet? arXiv:1902.10811
• Jimenez et al. (2024). SWE-bench: Can Language Models Resolve Real-World GitHub Issues? arXiv:2310.06770
• Jumper et al. (2021). Highly accurate protein structure prediction with AlphaFold. Nature 596.
• Berger & Leighton (1998). Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete. Journal of Computational Biology 5(1).
• Applegate, Bixby, Chvátal & Cook. The Traveling Salesman Problem (Concorde). math.uwaterloo.ca/tsp
• Christofides (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Carnegie Mellon University Technical Report.