skip to content

Why would one polynomial-time algorithm for a single NP-complete problem put every NP problem into P?

level: seniorimportance: nice to knowfreq 32%

answer

  1. polynomials compose
  2. transform, then solve
  3. the reduction already exists
  4. output no longer than the running time
  5. hardness is what carries it

basics

~20 s

Completeness means every NP problem already reduces into that one in polynomial time. Composing the polynomial transformation with the polynomial solver answers any NP problem in polynomial time, because polynomials compose and the transformed instance stays polynomially sized.

solid answer

~40 s

The hardness half of completeness says every problem in NP transforms into this one by a polynomial-time reduction, and those reductions already exist by definition — nothing has to be discovered. Given a polynomial algorithm for the complete problem, any NP problem is solved by two steps: run the reduction on the instance, then run the algorithm on its output. If the reduction costs `p(n)` its output is at most `p(n)` long, so a solver costing `q(m)` costs `q(p(n))` overall, and a polynomial of a polynomial is a polynomial. Every NP problem therefore lands in P, which is P equals NP. Note that the collapse rides on **hardness**, not membership: a polynomial algorithm for any NP-hard problem does the same.

go deeper

for a junior

Hold the shape: transform the instance, then solve the transformed one. Two polynomial steps in sequence are still polynomial overall.

for a middle

Explain why the transformed instance stays polynomially sized and why that size bound is what keeps the composed cost polynomial in the original input.

for a senior

Use this to explain why asking a team for a guaranteed polynomial exact algorithm on a complete problem is asking them to settle an open question, and why a good heuristic is not evidence either way.

for a principal

Frame the catalogue as one object when setting direction: a breakthrough on any complete problem would be a breakthrough on all, which is why hardness is treated as decisive rather than as a challenge to out-engineer.

## The setup Suppose someone produces a genuine polynomial-time algorithm — correct on every instance, with a proven polynomial bound — for one problem `C` that is NP-complete. The claim is that this single algorithm decides *everything* in NP in polynomial time. The argument is short, and its shortness is the point: completeness was designed to make it short. ## The two-step argument Take any problem `A` in NP and any instance `x` of it, of size `n`. 1. Because `C` is NP-hard, a polynomial-time reduction from `A` to `C` **already exists**. It is part of what being NP-hard means, so no search is needed; the mathematics does not care whether anyone has written it down. 2. Run that reduction on `x`, producing an instance `y` of `C` whose answer is yes exactly when `x`'s answer is yes. 3. Run the new algorithm on `y` and return its verdict. The verdict is correct because the reduction preserves the answer, and the whole procedure is polynomial because of one arithmetic fact spelled out below. So `A` is in P. Since `A` was an arbitrary member of NP, all of NP is in P, and since P is contained in NP, the two classes coincide. ## Why the composition stays polynomial This is the step worth stating carefully, because "polynomial plus polynomial" is where an intuitive version of the argument can go wrong. - The reduction runs in time `p(n)` for some polynomial `p`. A machine cannot write more output than it has steps, so the produced instance `y` has size at most `p(n)`. - The algorithm for `C` runs in time `q(m)` on an input of size `m`, so on `y` it costs at most `q(p(n))`. - Total cost is `p(n) + q(p(n))`. A polynomial composed with a polynomial is a polynomial, so the total is polynomial in the **original** size `n`. The size bound in the first bullet is what makes the composition safe. If a reduction were allowed to blow the instance up exponentially, the second step's polynomial would be a polynomial in an exponentially larger number, and nothing would follow — which is exactly why reductions in this setting are required to run in polynomial time rather than merely to be computable. ## Hardness carries the collapse, not membership A common mistake is to think the collapse needs `C` to be in NP. It does not. Step 1 uses only NP-hardness — the fact that all of NP reduces into `C`. So a polynomial-time algorithm for any NP-hard problem, complete or not, decision or otherwise phrased, would produce the same collapse. Membership matters for other things: it fixes the ceiling, and it makes `C` reusable as the source of later reductions. | Property of `C` | Needed for the collapse? | What it is needed for | |---|---|---| | NP-hard | Yes | The reduction from every NP problem into `C` | | In NP | No | Placing `C` inside the class, and the word complete | | A decision problem | No | Stating membership at all | ## What this means for a design review This is why asserting completeness for an internal feature is a heavier claim than it looks. It says the feature is as hard as every problem in NP simultaneously, so anyone who solves it in polynomial time has solved all of them — one of the central open questions. Three practical readings follow. - **Stop asking for an exact polynomial guarantee.** Requesting one is requesting a resolution of that open question, whether or not the document says so. - **A fast heuristic triggers nothing.** The collapse needs an algorithm that is correct on *every* instance with a proven polynomial bound. Something that is fast and usually right is neither, and is not evidence about P and NP in any direction. - **The catalogue is one object.** Because complete problems reduce into each other, a breakthrough on any one of them is a breakthrough on all of them, and the absence of such a breakthrough after decades of attention is the practical reason hardness is treated as a plan-changing result. The converse is also worth keeping straight: none of this proves the collapse cannot happen. It is a conditional, and the condition is open.

  • Why does the argument need the reduction to run in polynomial time rather than just to be computable?
    Because the produced instance can be no longer than the reduction's running time. A polynomial-time reduction yields a polynomially sized instance, so the solver's polynomial cost stays polynomial in the original input. An unbounded reduction could inflate the instance enough to make the second step worthless.
  • Would a very fast heuristic for one complete problem have the same consequence?
    No. The collapse needs an algorithm that is correct on every instance and provably polynomial. A heuristic that is fast and usually right fails both requirements, and its practical success says nothing about the relationship between P and NP.

saying these in an interview costs you the question

  • Thinks the collapse reaches only problems reduced by hand
  • Believes membership in NP is what carries the collapse
  • Assumes composing two polynomial steps can be superpolynomial
  • Says each NP problem would still need its own fast algorithm
  • Believes a fast heuristic would trigger the collapse