skip to content

A team's only evidence is an exponential-time algorithm for shift assignment; why does that not prove NP-hardness?

level: seniorimportance: should knowfreq 45%

answer

  1. upper bound versus lower bound
  2. our failure is not the problem's property
  3. evidence is a reduction, not a clock
  4. huge search space, polynomial algorithm
  5. hardness is conditional on an open question

basics

~20 s

An algorithm bounds one solution's cost from above; hardness is a claim about every possible algorithm. Only a polynomial-time reduction from an already-complete problem establishes it, and plenty of problems with exponential brute force turn out to be polynomial.

solid answer

~40 s

The evidence is the wrong shape. An exponential algorithm is an **upper bound** on what this team achieved; NP-hardness is a statement about **every** algorithm, including the ones nobody has thought of. The only accepted evidence is a polynomial-time reduction showing that an already-complete problem transforms into this one. History is full of problems whose obvious approach enumerates exponentially many candidates and which nevertheless have polynomial algorithms, so "our search space is huge" is not evidence either. Note the reverse trap too: even a correct NP-hardness proof is not an exponential lower bound. It says there is no polynomial exact algorithm unless P equals NP, which is a conditional statement about an open question, not a proven running-time floor.

go deeper

for a junior

Remember that writing a slow program says something about the program, not about the problem. Hardness has to be proved by transforming a known hard problem.

for a middle

Explain the direction of each bound: an algorithm is an upper bound, hardness constrains all algorithms, and only a reduction establishes the latter.

for a senior

In review, separate the operational sentence about today's solver from the classification claim, and refuse the search-space-size argument, which applies verbatim to problems known to be easy.

for a principal

Set the standard for what a document may assert from measurement alone, so teams do not convert benchmark pain into a hardness claim that later blocks a viable exact approach.

## The two bounds point in opposite directions A running-time claim can bound a problem from two sides, and confusing them is the defect here. - An **algorithm** gives an **upper bound**: there exists a way to solve this in at most this much time. Writing a faster one tomorrow lowers it. - **Hardness** is a **lower bound** in spirit: a claim that binds *every* algorithm, including all the ones nobody has written. No amount of evidence about one algorithm can establish it. So "our exact solver is exponential" is a true, useful, entirely local fact. It describes the team, not the problem. The review question is not how slow the current code is; it is what is known about the problem underneath it. ## What the accepted evidence looks like Hardness is established by **reduction**: a polynomial-time transformation taking instances of a problem already known to be complete for NP and producing rostering instances with the same yes/no answer. Because everything in NP already reduces into that established problem and reductions compose, everything in NP then reduces into rostering. That is the entire proof technique, and it is why the argument is structural rather than empirical — no timings, no benchmarks, no failed search appears in it. This also explains why the discipline is unforgiving about the source problem: transitivity only carries hardness that was already there. ## Why a big search space proves nothing The intuition "there are exponentially many rosters, so it must be hard" fails on its own terms, because the number of candidates and the cost of finding the best one are different quantities. Pairing problems, ordering problems and several constraint problems all have exponentially many candidate configurations and admit polynomial algorithms that never enumerate them — bipartite matching is the standard example of a problem whose naive search is exponential and whose real algorithm is not. Structure, not count, decides. A useful check before accepting the intuition: 1. Does the argument mention anything about the problem's structure, or only about the size of the candidate set? 2. Would the same argument apply verbatim to a problem known to be in P? If yes, the argument proves nothing. 3. Has anyone actually tried to find the polynomial algorithm, or did the search stop at the first brute force? ## The mirror-image error The opposite overstatement is just as common in review: reading a *correct* hardness proof as a proven exponential lower bound. It is not. NP-hardness says: > No polynomial-time exact algorithm exists **unless** P equals NP. That is conditional on an open question. It does not forbid an algorithm that runs in time that is subexponential, or polynomial on every instance the system actually receives, or exponential only in some small structural quantity. Problems for which a superpolynomial lower bound really is *proven* exist — they are complete for classes provably larger than P — but NP-complete problems are not among them, and claiming otherwise in a document is a factual error that a careful reader will catch. ## Reading the evidence in a review | Evidence offered | What it supports | What it does not support | |---|---|---| | Our exact solver is exponential | Our current code is slow | Anything about the problem | | The search space is exponential | The naive method is unusable | That no polynomial method exists | | Benchmarks got worse with input size | An empirical growth trend | A claim about all algorithms | | A polynomial reduction from a complete problem | NP-hardness | A proven exponential lower bound | | A reduction plus a polynomial verifier | NP-completeness | A proven exponential lower bound | ## What to ask for instead If the team wants the hardness conclusion, the request is specific and small: name the decision version, name the established complete problem, and show the transformation and why it preserves the answer in both directions. If they cannot, the honest sentence for the document is "we have not found a polynomial algorithm", which is a statement about effort and can be revisited — quite different from a statement about the problem, which cannot.

  • Are there problems with a proven superpolynomial lower bound?
    Yes — problems complete for classes provably larger than P are provably not solvable in polynomial time. NP-complete problems are not in that situation: their intractability is conditional on P not equalling NP, which remains open, so a hardness proof is never a proven running-time floor.
  • The team's solver is exponential and a reduction proof also exists. Does the timing evidence add anything?
    Not to the classification, which rests entirely on the reduction. Timings are still useful operationally: they say what today's instances cost and whether the exact approach is viable at current sizes. Keep the two claims in separate sentences so the document does not appear to argue hardness from benchmarks.

saying these in an interview costs you the question

  • Offers a slow algorithm as evidence of NP-hardness
  • Reads NP-hard as a proven exponential-time lower bound
  • Assumes an exponential search space rules out a polynomial algorithm
  • Concludes hardness from a failure to find something faster
  • Treats benchmark growth as a claim about every algorithm