skip to content

Why is it wrong to say that a problem being in NP means it takes exponential time to solve?

level: middleimportance: must knowfreq 65%

answer

  1. the letters are an abbreviation, not a verdict
  2. membership is decided by checking cost
  3. easy problems live in there too
  4. best known is not proven best
  5. a lower bound here would win the prize

basics

~20 s

NP is defined by cheap checking, not by expensive solving. Every polynomial-time problem is already inside NP, and for no NP-complete problem has anyone ever proven a superpolynomial lower bound; exponential is the best known cost, not a floor.

solid answer

~40 s

NP is the class of decision problems whose yes-instances carry a short certificate that a polynomial-time check accepts. That definition says nothing about the price of finding the certificate. `P` sits inside `NP`, so sorting and shortest paths are in NP too, and nobody calls those exponential. Even for the hardest members, exponential running time is the best algorithm we currently know, not a proven lower bound: no superpolynomial lower bound has ever been established for an NP-complete problem, and establishing one would separate P from NP and settle one of the Clay Millennium Prize Problems. The accurate sentence is 'no polynomial-time algorithm is known for it, and one exists only if P equals NP'. The letters also abbreviate nondeterministic polynomial, not non-polynomial.

go deeper

for a junior

Remember what the two letters abbreviate and that membership is about how cheaply a proposed answer can be checked. Knowing that easy problems are also inside the class is enough to avoid the usual slip.

for a middle

Explain the containment of polynomial-time problems inside the class, and separate 'the best algorithm we know is exponential' from 'exponential cost is proven'. Say plainly that no superpolynomial lower bound exists for any complete problem.

for a senior

When someone on the team declares a requirement impossible because it is NP-complete, restate the claim precisely: no general polynomial method is known, worst case over all inputs. Then ask what the real instances look like before anything is abandoned.

for a principal

Watch for this conflation in design arguments where it has consequences — a security claim resting on worst-case hardness, or a roadmap that writes off a feature on the strength of a label. Decide which claims your architecture is allowed to lean on.

## The name is an abbreviation, not a prediction `NP` abbreviates **nondeterministic polynomial time**. It collects decision problems — questions with a yes or no answer — for which a *yes* instance has a short piece of supporting evidence that a deterministic procedure can check in time polynomial in the size of the input. The class is therefore defined entirely by the cost of **checking**. Nothing in the definition mentions the cost of producing the evidence, and nothing in it mentions an exponential. Much of the confusion is purely linguistic: the two letters look like a contraction of 'non-polynomial', and they are not. ## Three independent reasons the slogan fails 1. **P is contained in NP.** Anything solvable in polynomial time is trivially in NP: ignore the offered evidence and just solve it. Sorting a list, finding a shortest path, deciding primality, solving a linear program — all of them are members of NP. If membership implied exponential cost, these would be exponential, which is plainly false. 2. **For the hardest members, exponential is an upper bound, not a proven lower bound.** No superpolynomial lower bound has ever been proven for any NP-complete problem. Proving one would immediately separate P from NP. So 'this needs exponential time' is a statement about the current state of human knowledge, not a theorem. 3. **Known algorithms are frequently not plain exponential either.** Some NP-complete problems admit algorithms whose cost is exponential only in a parameter that is small in practice, and the classic numeric ones admit dynamic programs whose cost is polynomial in the numeric magnitude of the input rather than in its encoded length. The blanket word 'exponential' hides all of that structure. ## The three claims that get conflated | Claim | What it actually says | Proven? | |---|---|---| | The problem is in NP | Yes-instances have polynomially checkable evidence | Yes, once you exhibit the check | | The problem is NP-complete | It is in NP, and every NP problem maps into it in polynomial time | Yes, for a large catalogue of problems | | The problem requires exponential time | No polynomial algorithm exists for it | **Never proven for any NP-complete problem** | The first two are settled facts about specific problems. The third is an open question in every single case, and it is open in a very strong sense: a single proof of it would resolve the whole P versus NP question at once. ## What the label does license you to say - No polynomial-time algorithm is known for this problem, and none is known for any of the thousands of problems equivalent to it. - If one were found, all of those problems would become polynomial simultaneously, which is why the absence of one after decades of effort is treated as strong evidence. - The hardness statement is about the **worst case over all instances of every size**. It is not a statement about the instances a given system actually receives. - A superpolynomial lower bound for this problem would separate P from NP; nobody has one. ## Where exponentials do legitimately enter There is a real exponential upper bound, and it comes from the definition rather than from any cleverness: the evidence has polynomial length, so a machine can enumerate every candidate of that length and check each one, which places NP inside exponential time. That is the honest source of the association — brute force over certificates costs exponentially, so exponential is the naive ceiling. The classes strictly above NP are a different subject: some separations between resource-bounded families genuinely are proven, and which of the classes clustered around NP are distinct from one another is the material of the inclusions and separations leaf, not this one. ## Why the sloppy phrasing costs you in an interview An engineer who says 'it is NP, so it is exponential' has compressed three distinct claims into one and asserted an open problem as settled fact. The follow-up an interviewer asks next is usually some version of 'so what is proven here?', and the candidate who answers 'no polynomial algorithm is known, and no superpolynomial lower bound is proven either' has demonstrated they understand what the open question actually is. The candidate who doubles down has revealed they learned a slogan. The same sloppiness has practical consequences: it leads people to abandon a problem whose real instances are small or structured, and it leads them to trust a security argument built on worst-case hardness, which is a different mistake with a larger blast radius.

  • If no exponential lower bound is proven, why do engineers still treat an NP-complete label as bad news?
    Because decades of effort across a huge catalogue of equivalent problems have produced no polynomial algorithm for any of them, and one would give polynomial algorithms for all of them at once. The label is strong evidence about the state of knowledge, plus a warning that a fast general method would be a mathematical event rather than a clever afternoon.
  • Does an NP-complete label mean the instances your system actually receives are out of reach?
    No. Hardness is a worst-case statement quantified over all instances of every size. Real inputs are often small, sparse or otherwise structured, and some of the classic numeric problems have dynamic programs whose cost tracks numeric magnitude rather than encoded length. The label says no general fast method is known, not that a particular workload is hopeless.
  • What would a proof that some NP-complete problem needs superpolynomial time establish?
    That P and NP are different classes. Every NP problem maps into an NP-complete one in polynomial time, so a polynomial algorithm for the complete problem would give one for all of NP; a superpolynomial lower bound for it therefore rules out P equalling NP. That single proof would settle the open question in the direction most researchers expect.

A slush pile where every submission comes with a one-page summary a reader can skim in a minute says nothing about how long the manuscript took to write. The pile is sorted by how fast a claim can be checked, not by how hard it was to produce.

saying these in an interview costs you the question

  • Says the letters NP stand for non-polynomial
  • Claims every problem in NP needs exponential time
  • Believes exponential cost is a proven lower bound for NP-complete problems
  • Thinks P and NP are disjoint classes with nothing in common
  • Treats a worst-case hardness label as a statement about their own inputs