P versus NP
P vs NP and Artificial Intelligence: Why AI Can’t Solve Everything (Yet)
In April 2025, J. Connell ran a small experiment. He asked ChatGPT-4 to review a dozen published papers that claimed to have finally cracked P versus NP. The AI didn’t flag any major flaws.…
In April 2025, J. Connell ran a small experiment. He asked ChatGPT-4 to review a dozen published papers that claimed to have finally cracked P versus NP. The AI didn’t flag any major flaws. Instead, it complemented parts of the method and even said some of the ideas made sense. That reaction puzzled Connell, because around the same time, computer scientist Lance Fortnow was telling audiences something very different: no matter how advanced our models get, true general intelligence may always remain out of reach. Even if someone somehow proved P = NP, Fortnow said, the dream of all-knowing AI probably wouldn’t follow.
And that tension points to something real. Today’s AI can talk like us, beat champions at complex games, and predict how proteins fold. But throw an NP-hard problem at it, one of those messy tasks humans often navigate with intuition or a flash of insight, and the system stalls.
The reason lies deep in computational complexity theory. These unresolved questions about what can or can’t be solved efficiently set hard boundaries for every algorithm we build, no matter how fancy the neural network.
For people building AI products, this isn’t just theory. It’s a reminder that success depends on knowing where the technology’s limits truly are, and not getting swept away by promises it can’t fulfil.
How NP Problems Limit AI Model Training
Training a large AI model sounds straightforward from the outside: feed it data, let it learn, watch it improve. But behind the scenes, it’s a messy search through a gigantic maze. Each weight in the network is a dial you can turn, and modern models have billions or even trillions of them. Finding the right combination is like trying to locate a tiny target somewhere in a landscape full of dead ends. Gradient descent helps guide the search, but it isn’t magical. It often settles in the first small valley it finds instead of the deepest one. That’s why two models trained the same way can behave differently; each wandered into a different part of the maze.
Researchers have invented clever shortcuts over the years: momentum to push past small bumps, adaptive learning rates to speed up or slow down when needed, and architecture tricks like skip connections and attention. These tricks make the journey manageable, but they don’t change the fact that the landscape is fundamentally hard to navigate.
If the world suddenly learned that P = NP, everything would change. We’d have efficient algorithms to find the absolute best parameters for a model. But in reality, we’re still stuck with the complexity we have. More GPUs help, but they can’t erase the underlying hardness built into these optimisation problems.
Neural Architecture Search: The Meta-Problem That's Even Harder
Training a neural network is hard enough when the architecture is fixed. But once you start searching not just for the right weights but for the right design itself, things quickly become overwhelming. That’s what Neural Architecture Search aims to handle: letting an algorithm explore a vast number of possible network designs without relying entirely on human intuition.
At first glance, it sounds perfect, just let the machine find the best layout. But the number of possible designs grows incredibly quickly. Even a small five-layer network with a handful of options per layer can create tens of thousands of possibilities. Add more depth or more choices, and the number skyrockets.
Researchers have found ways to control the explosion. Google’s LayerNAS dramatically reduced search time by adding smart constraints at each layer. Efficient NAS avoids retraining every candidate by letting different architectures share weights. Differentiable NAS uses gradients to guide the search, turning rigid design choices into something smooth enough to optimise.
These tricks help, but they don’t remove the underlying difficulty. The space of possible architectures is enormous, and finding the single best one is an NP-hard problem, meaning no efficient method is known. So today’s NAS systems rely on heuristics: reinforcement learning, evolutionary search, and Bayesian methods. They often discover impressive architectures, but they can’t promise they’ve found the best possible design.
Optimisation Limits: Why AI Can't Guarantee Best Solutions
In everyday AI systems, there’s a big difference between finding a pretty good answer and finding the best possible one. And the reason we rarely get the best answer goes back to P versus NP. Think about the recommendation engines that decide which videos you see or which products show up in your feed. Behind the scenes, they’re trying to balance dozens of competing goals: engagement, variety, freshness, and business targets across millions of people. The math behind that juggling act is NP-hard, so even the most advanced AI can only search smartly and hope for strong results, not perfect ones.
The same problem shows up in delivery routing, job scheduling, cloud resource management, and even in financial trading. AI makes these systems far better than they used to be, but it still can’t guarantee the single best solution. Neural networks and clever heuristics narrow the search space and speed up the process, but they don’t remove the basic mathematical difficulty.
These limits even affect AI safety. Trying to shape an AI system so that it reliably follows human values is an extremely hard optimisation problem, and that’s before you get to the challenge of defining “human values” in the first place. Techniques like RLHF and constitutional AI help guide models in the right direction, yet none can claim to have found the perfect answer.
AI can give us good solutions, often incredibly good ones. But the quest for guaranteed optimality runs straight into the walls built by NP-hard problems.
Why AGI Depends on P vs NP (And Probably Won't Arrive Soon)
The idea of artificial general intelligence, machines that think and understand the world as we do, runs into some surprising roadblocks. Lance Fortnow, a well-known computer scientist, has even said he doubts we’ll reach full AGI, and he’d still say that even if someone proved P = NP. It sounds strange, but his reasoning cuts to the heart of what intelligence is.
Humans solve all kinds of problems: we invent new ideas, make sense of ambiguous situations, learn from very little information, and apply what we know to completely new contexts. A machine that could do all of this would have to navigate problem spaces that are, mathematically speaking, incredibly hard. Many of them look like NP-hard search problems, problems for which no efficient solution is known. Humans get by using intuition and rough shortcuts. We don’t compute our way to perfect answers; we just get answers that work well enough. But that kind of intuition is hard to turn into code.
Today’s AI models shine when the rules are clear, and there’s plenty of data. They struggle when the world gets messy, when common sense, causality, and flexible reasoning are required. If general intelligence demands efficient solutions to NP-hard tasks, then a purely computational route to AGI might be blocked by the math itself. And then there’s consciousness. We don’t have a solid definition of it, and we don’t know whether it’s something computers can generate or just simulate. It might rely on computations we don’t yet understand, or on something that isn’t computational in the first place.
AI has come a long way, and the progress is real. But the gap between today’s systems and true, human-like intelligence remains wide, and the obstacles may be deeper than they first appear.
How P Equals NP Would Change AI Forever
Most people in computer science think P probably doesn’t equal NP. But imagining a world where it does is a useful thought experiment, because it shows just how much today’s AI systems are limited by basic math.
If someone proved P = NP and actually gave us efficient algorithms, everything about AI would change overnight. Training models wouldn’t rely on gradient descent or hope for a decent local optimum. We’d be able to compute the best possible parameters directly. Entire families of neural-network innovations, attention, transformers, and residual blocks, might suddenly look outdated if we could automatically design perfect architectures for any task.
Search and reasoning would jump to a whole new level. Chess, Go, protein folding, scheduling problems, anything that can be written as an NP-complete problem would become straightforward to solve. Many of the hardest challenges in science and engineering would fall quickly.
But this still might not give us AGI. Fortnow argues that true intelligence may involve things that aren’t captured by NP problems at all. Human common sense, context understanding, consciousness, none of these automatically pop out just because you can solve NP-complete problems efficiently. Even so, the scientific impact of P = NP would be enormous. Drug development, materials science, logistics, and many other fields would leap forward instantly. But the deeper puzzle of how to build a mind like ours might still be unsolved.
The Path Forward: Embracing AI's Bounded Capabilities
Seeing AI through the lens of P vs NP makes a lot of things clearer. It shows why AI is so good at some tasks and why it hits hard limits in others. When the problem is narrow, well-defined, and backed by lots of data, AI keeps getting better, such as image recognition, language models, recommendations, and autonomous systems. These areas will continue to advance. But expecting AI to match human general intelligence or solve every optimisation problem perfectly misses the math. Some issues are simply too complex to guarantee the best answer, no matter how much computing power you throw at them.
For entrepreneurs, this is actually useful. It means you can stop chasing AGI narratives and instead focus on building products where AI’s strengths really matter. Build systems that make people better at their jobs. Don’t blame engineering when a problem turns out to be mathematically impossible to optimise.
P vs NP also reminds us not to over-predict the future. Sure, if P = NP were proven, everything would change. But what’s more likely is continued improvement in heuristics and approximations, tools that make hard problems less painful but never fully solvable.
The takeaway? AI is incredibly powerful, but it’s not magic. Knowing its limits helps founders plan realistically, set healthy expectations, and make smarter decisions in a field that often gets swept up in hype.
___________
Discover sharp insights on AI, innovation, and the future of entrepreneurship. Explore ideas that elevate your thinking and sharpen your strategy. Only on Inspirepreneur Magazine.