In an interview a few years ago, a candidate spent five minutes lecturing me on whether P = NP. They wanted to make sure I knew it was an open problem. I knew. The candidate was a strong engineer in every other way, but the topic they had chosen to demonstrate computer-science depth was a topic I had used in production exactly zero times in a decade of writing software. I have used Theta(n log n). I have never once shipped code where the question "is this problem in P or NP?" was a productive thing to ask. The complexity classes you read about in textbooks are real, and they shape what is possible. They almost never shape what you are doing today.
This article is my attempt to give the honest version of P, NP, NP-hard, and NP-complete to working engineers. What each one means in plain words, where the recognition signal does pay off, and why I push back when juniors over-index on this material.
P, NP, and the things they actually claim
P is the class of decision problems solvable in polynomial time. "Decision problem" means a question with a yes-or-no answer; "polynomial time" means you can solve it in O(n^k) for some fixed k. Sorting a list, checking if a graph has a cycle, finding shortest paths, checking primality (this last one was a result I found genuinely surprising when it was proved in 2002): all in P.
NP is the class of decision problems whose yes-instances can be verified in polynomial time, given a hint. "Hint" here is a candidate solution; "verified" means you can check the candidate is correct in polynomial time. Sudoku is in NP: given a candidate filled-in board, you can check the rules in linear time. Subset Sum is in NP: given a candidate subset, you can sum it and compare to the target in linear time. Most problems we care about are in NP, because most problems we care about have polynomial-time verifiers.
The famous open question is P = NP: are all problems whose solutions can be verified quickly also solvable quickly? The general consensus among complexity theorists is no, but no one has proved it. A million-dollar prize sits on the proof.
For our purposes, the practical content of "this problem is in NP" is: "we can verify a guess fast, but we do not know how to find one fast". That is the signal that catches my attention in code review.
NP-hard and NP-complete
NP-hard is the class of problems that are at least as hard as the hardest problems in NP. Concretely: if you could solve any NP-hard problem in polynomial time, you could solve every NP problem in polynomial time. Halting problem is NP-hard (and in fact much harder; it is undecidable). Travelling salesman in its optimisation form is NP-hard.
NP-complete is the intersection: problems that are both in NP (verifiable in polynomial time) and NP-hard (at least as hard as everything in NP). These are the canonical "hard" problems. SAT was the first proven NP-complete problem (Cook-Levin, 1971). Sudoku, 3-coloring, subset sum, the decision version of TSP: all NP-complete.
The visual mental model:
P sits inside NP. NP-complete sits inside NP but outside P (assuming P != NP). NP-hard extends out past NP to include things that are hard but not even verifiable in polynomial time.
If P = NP, the inner P circle expands to fill all of NP, and NP-complete collapses into P. If P != NP, the picture above is the correct one.
Why I rarely care at work
In the kind of work most engineers do (web services, data pipelines, internal tooling, product features), the problems we solve are almost always in P. We sort, we filter, we aggregate, we hash, we route, we render. Every subroutine I write in a normal week has a known polynomial-time algorithm. The complexity-class question does not arise because there is nothing to compare against; we are firmly inside P.
The cases where complexity classes do come up are specific.
If I am implementing constraint solving, scheduling, planning, packing, or anything that resembles an optimisation problem with combinatorial structure, the underlying problem is often NP-hard. In those cases, "this problem is NP-hard" is a useful sentence because it tells me to stop looking for the optimal-and-fast algorithm; one does not exist (assuming P != NP). Instead I should reach for an approximation algorithm, a heuristic, a SAT or ILP solver, or accept that the input size has a low ceiling.
If I am writing security code, asymmetric cryptography depends on certain problems (factoring, discrete log) being hard. Those problems are believed to be outside P, though they are not believed to be NP-complete either; they sit somewhere in between. Knowing that the security guarantee comes from "the best known algorithm is exponential" is essential context.
If I am building or reviewing automation around test generation, model checking, or program verification, those tools internally solve NP-hard problems and you need to be aware of when their input size is going to make them blow up.
Outside those niches, the entire conversation about P and NP rarely arises in production code. The performance discussion is about constant factors, cache locality, network round trips, allocation pressure: things that do not show up in any complexity class.
The recognition signal that does matter
Here is where this material does pay off. Sometimes a junior engineer comes to me with a problem that, after some squinting, turns out to be a known NP-hard problem in disguise. The classical examples I have seen:
- "Pack these tasks into the smallest number of CI runners that fit a time budget" (bin packing).
- "Choose a subset of feature flags such that this rule fires" (subset sum / SAT).
- "Find an order for these database migrations that respects all of these dependencies AND minimises some cost metric" (TSP-like).
- "Pick the cheapest set of microservices that covers all of these capabilities" (set cover).
Recognising the shape of a problem as NP-hard is a permission slip. It tells the engineer not to feel bad about their failure to find a fast exact algorithm; one is not known to exist. It also tells them to switch strategies: pick a greedy heuristic, use a constraint solver, restrict the input size, or change the problem so the hard version does not arise. Without that recognition, they might burn weeks trying to find the trick.
The signal goes the other way too. If a junior comes to me convinced their problem is NP-hard, my first response is "are you sure? Did you check the polynomial-time-solvable variants?" Many problems have a hard general form and a tractable restricted form. Maximum independent set is NP-hard on general graphs; in interval graphs it is solvable in O(n log n). Shortest path is in P; shortest path with negative cycles is NP-hard. The same problem can be in or out of P depending on small constraint changes, so the framing matters.
A worked example: when the class question helped
A team I was on once had to assign incoming support tickets to engineers, optimising for "minimise the maximum load on any one engineer" subject to "engineers have skills, tickets need skills". The naive person on the team (who was me, three years prior) would have tried to write a clever exact algorithm. The senior engineer said, "this is multi-machine scheduling with constraints, and the general problem is NP-hard. Stop. We are going to use a simple greedy heuristic that gets within 20% of optimal, and we are going to ship it next week."
That was the moment "is this problem in NP-hard?" was actually a productive question. The answer "yes" did not solve the problem, but it changed the planning: the team stopped trying to be clever, used a known approximation, and moved on. Without the complexity-class context, we might have spent another month trying to optimise.
The misuse I see most often
Engineers who have read about NP-hard sometimes apply it as a thought-stopper. "Oh, that's NP-hard, can't be done." That is not what NP-hard means. NP-hard means there is no known polynomial-time exact algorithm. It does not mean the problem is intractable in practice. Many NP-hard problems have:
- Very fast solvers in practice for typical inputs (modern SAT solvers handle problems with millions of variables routinely, even though SAT is
NP-complete). - Tractable special cases (the
2-SATrestriction is inP). - Approximation algorithms that get within a constant factor of optimal.
- Tractable behaviour when the input is small (which it usually is in production).
So when an engineer says "we can't do this, it's NP-hard", my response is: "small input, so we can brute-force? Special structure, so we have a polynomial-time variant? Acceptable approximation, so we can use a heuristic? Or do we genuinely need an exact answer at scale, in which case we have to redesign?" Most of the time, one of the first three works.
What I do tell juniors about NP
When a junior engineer asks me about complexity classes, here is what I tell them.
Memorise the definitions cleanly. P is "solvable fast", NP is "verifiable fast given a hint", NP-hard is "at least as hard as the hardest of NP", NP-complete is the intersection. That is the whole vocabulary; everything else is decoration.
Recognise the canonical hard problems by shape: SAT, subset sum, knapsack, set cover, vertex cover, graph coloring, TSP, bin packing. If a problem in your work resembles one of these, suspect NP-hardness and check.
Use the recognition as a planning tool, not a wall. The reduction from "this is NP-hard" to "we will use a greedy heuristic / approximation / solver / size cap" is the productive move. The reduction to "we cannot do this" is wrong almost every time.
Do not bring up P = NP in casual technical conversation. It is real, it is open, it is a million-dollar problem, and it is also a topic that makes you sound like you are pattern-matching to "things smart engineers say" rather than thinking about your actual code. The problems you ship are in P ninety-nine percent of the time, and on the rare occasions they are not, the conversation that matters is "what heuristic do we use", not "is the conjecture true".