P vs. NP: the Million-dollar Question (Literally!)

P vs. NP asks whether every problem whose solution a computer can check quickly (NP) can also be solved quickly by one (P). Formally posed in 1971, it is one of the seven Millennium Prize Problems, and the Clay Mathematics Institute will pay $1 million for a correct proof either way. It remains unsolved.

P vs. NP at a Glance

The Spectrum of Problem-solving

The easiest way to understand P vs. NP is to picture every computational problem sitting somewhere on a line, from easy on the left to brutally hard on the right. We’ll build that line one concept at a time.

First, what does “easy” mean to a computer scientist? It isn’t about how long a problem takes today. It’s about how the running time grows as the problem gets bigger. An easy problem’s running time grows polynomially — like n² — so doubling the input makes the work a manageable multiple larger. A hard problem’s running time grows exponentially — like 2ⁿ — so every additional item doubles the work.

That difference is small at first and then enormous:

A faster computer doesn’t rescue you from the right-hand column. That’s why computer scientists care so much about which side of the line a problem lives on.

P: Predictable Problems

P is the set of problems a computer can solve in polynomial time — the “easy” problems. Sorting a list of names alphabetically is a classic example: even a list of a million names sorts in a fraction of a second, and a list twice as long takes only a little more than twice as long.

P problems are, frankly, a little boring. That’s a compliment. When a problem is in P, you know a reliable, efficient method exists, and you can scale it up without surprises. Finding the shortest driving route between two cities, multiplying two numbers, and solving a linear program (proven polynomial by Khachiyan in 1979) are all in P.

NP: Challenging, But Solvable Problems

NP is the set of problems where, if someone hands you a proposed solution, you can check whether it’s correct in polynomial time. Finding the answer may be hard; verifying it is easy.

Three familiar examples make the idea concrete:

• Sudoku. Filling in a blank grid can take real effort. Checking a completed grid takes seconds: scan every row, column, and box for repeats.
• Tetris. Given a known sequence of pieces, can you place them all without topping out? Hard to plan. Easy to check if someone shows you the placements.
• Super Mario Bros. Can Mario reach the flag? Hand someone a winning move list and they can replay it. (Mario turns out to be a special case — more on that below.)

Two clarifications matter here. First, every P problem is also in NP: if you can solve a problem quickly, you can certainly check an answer quickly — just solve it again and compare. So P sits inside NP. Second, the “N” doesn’t stand for “not.” NP stands for nondeterministic polynomial time, a technical nod to a hypothetical computer that could guess the right answer and then verify it.

The entire P vs. NP question lives in the gap between checking a solution and finding one.

NP-hard: the Really Tough Problems

A problem is NP-hard if it is at least as hard as the hardest problems in NP. If you had a fast method for an NP-hard problem, you could use it to solve every NP problem quickly.

NP-hard problems are the bad boys of the spectrum. Some sit inside NP. Others sit entirely outside it — problems so difficult that even checking a proposed solution can’t be done quickly.

Super Mario Bros. is a good illustration. In 2012, researchers proved that generalized Super Mario Bros. (with levels of arbitrary size) is NP-hard. In 2016, Demaine, Viglietta, and Williams went further and proved it is PSPACE-complete — a class widely believed to be harder than NP, because a winning move list can be astronomically long and impractical to verify.

NP-complete: the Key to Solving NP Problems

NP-complete problems are the problems that are both in NP and NP-hard. They sit right on the border: solutions are easy to check, and the problems themselves are as hard as anything in NP.

What makes NP-complete problems special is their master-key property. Every NP problem can be translated, or reduced, into any NP-complete problem in polynomial time. So if anyone ever finds a fast algorithm for a single NP-complete problem, that algorithm unlocks every problem in NP.

Stephen Cook identified the first NP-complete problem, Boolean satisfiability (SAT), in 1971. A year later, Richard Karp showed that 21 more classic problems were NP-complete. Today there are thousands, including two from our examples:

• Tetris (offline version, with a known piece sequence) — proven NP-complete by Demaine, Hohenberger, and Liben-Nowell in 2003
• Sudoku (generalized to n² × n² grids) — proven NP-complete by Yato and Seta in 2003

Note that these results apply to generalized versions of the games. A standard 9 × 9 Sudoku is small enough that a computer solves it instantly; the hardness shows up as the grid grows.

The Enigma of P vs. NP: is There a Shortcut to Solving Hard Problems?

Nobody knows whether P equals NP. No one has found a polynomial-time algorithm for any NP-complete problem, and no one has proven that such an algorithm cannot exist.

If P = NP, then every problem whose solution is easy to check is also easy to solve, and the “hard” region of our line collapses into the easy one. If P ≠ NP, then some problems are fundamentally harder to solve than to verify, and no amount of cleverness will change that.

The Clay Mathematics Institute named P vs. NP one of its seven Millennium Prize Problems in 2000 and offers $1 million for a correct proof either way (claymath.org). Of the seven, only the Poincaré conjecture has been solved. Claimed P vs. NP proofs appear regularly; none has survived peer review.

Most researchers lean toward P ≠ NP. In William Gasarch’s 2019 survey of theorists, 88% said they believe P ≠ NP, up from 61% in his 2002 survey. But belief isn’t proof, and the question stays open

Why P vs. NP Matters for Supply Chain Planning

Many of the core problems in supply chain planning are NP-hard. That means there is no known master key — no general method that finds the provably best plan quickly as the business grows. Real-world planning depends on creative, tailored algorithms that find excellent plans in the time planners actually have.

Which supply chain planning problems are NP-hard?

Supply chain planning problems become NP-hard the moment they involve discrete decisions: which plant, which sequence, how many batches, run or don’t run. Each one maps to a classic problem from the complexity literature:

The combinations grow fast. Sequencing just 20 products on a single line has 20! possible orders — about 2.4 quintillion (2.4 × 10¹⁸). Checking one sequence is easy. Checking all of them isn’t possible.

There’s a useful nuance here: the purely linear versions of some of these problems, like a simple blend or a continuous product mix, are linear programs and sit comfortably in P. It’s the real-world details — minimum run sizes, changeovers, whole trucks, whole batches — that push them into NP-hard territory. And real-world planning is all details.

How do planners solve NP-hard problems in practice?

Planners solve NP-hard problems by trading a guarantee of the perfect answer for a very good answer delivered in time to use it. A near-optimal plan in minutes beats an optimal plan next month. The main approaches are:

• Mathematical optimization (linear and mixed-integer programming) to find optimal or provably near-optimal plans for well-structured problems
• Decomposition to break a large problem into smaller linked pieces — for example, planning monthly capacity first, then sequencing within each week
• Heuristics that encode proven rules of thumb and planner expertise to find strong plans fast
• Hybrid methods that combine all three, using heuristics to build a starting plan and optimization to improve it

There is no single algorithm that works for every supply chain, because the problems aren’t identical. A chemical producer’s campaign schedule, a food manufacturer’s shelf-life-constrained allocation, and a CPG company’s distribution network each have their own structure — and the best algorithms exploit that structure.

How Arkieva approaches hard planning problems

Arkieva builds planning algorithms around the structure of each customer’s supply chain rather than forcing every problem through one generic solver. Arkieva Supply Planning combines optimization, decomposition, and heuristics to handle campaign and cycle planning, product mix, allocation, sequencing, cutting, and blending for process manufacturers, chemical companies, and CPG and food and beverage producers.

The goal isn’t to win the $1 million. It’s to give planners a plan they can trust, fast enough to act on, and flexible enough to re-run when the next disruption hits. For more on how these methods show up in day-to-day planning, see process manufacturing, production scheduling and the Arkieva planning platform.

Frequently Asked Questions

Hard Problems Deserve Better Than Rules of Thumb

P vs. NP may never be settled, but supply chain planners can’t wait for mathematicians. The practical question is whether your planning tools are built to handle NP-hard problems intelligently — or whether your team is filling the gap with spreadsheets and guesswork. [Arkieva S&OP Management] [LINK: arkieva.com S&OP Management solution page — confirm URL] brings those plans together so decisions reflect what your supply chain can actually do.

Ask for a one-on-one demo of the Arkieva supply chain planning solution → Request a Demo