skip to content

Reporting a requirement as NP-hard to stakeholders — what must that verdict carry to be honest and actionable?

level: seniorimportance: should knowfreq 42%

answer

  1. the label is heard three different ways
  2. which version did you classify?
  3. matched or proved — say which
  4. state n and where the cliff sits
  5. name what would change your mind

basics

~20 s

A usable verdict names which version of the problem was triaged, the evidence tier behind it — matched against a known problem, or proved — the input sizes and exactness it assumes, and what would overturn it. The label alone is not a plan.

solid answer

~40 s

Four things travel with the verdict. **Which version**: exact optimum or good-enough, decision or optimisation, and which clauses were included — dropping one often changes the answer. **The evidence tier**: "this contains a known hard problem, which I matched but did not prove" is a different statement from a proof, and the hedge is part of the honesty. **The operating assumptions**: at the sizes we expect, what is still cheap, and where the cliff is. **The falsifier**: what would change my mind — a guaranteed bound, an input shape, a relaxed objective. I also avoid the word *impossible*, because NP-hard instances are solved routinely at modest size; the accurate sentence is about how the cost grows and what we would trade away.

go deeper

for a junior

Learn the vocabulary difference before using it in front of stakeholders: hard means expensive as inputs grow, not unsolvable. Misusing the stronger word costs credibility that is hard to recover.

for a middle

Be able to state the verdict with its assumptions attached: which version you classified, what n is, and how confident the evidence makes you.

for a senior

Show the whole report: the version, the hedge, the envelope, the falsifier, and the decision the verdict unblocks — plus the cheap experiment that locates the real cliff.

for a principal

Frame the verdict as a requirement negotiation rather than a technical finding, and make sure it is recorded where the requirement lives so the constraint survives the next change.

## Why the label alone is useless A spike that reports one word — "NP-hard" — leaves everyone who reads it with the same options they had before: guess, escalate, or ignore it. Worse, the word is heard differently by different readers. Engineers hear *expensive at scale*. Managers hear *impossible*. Someone recalling half a lecture hears *proven exponential*. A verdict that can be heard three ways is not a verdict, and the failure to qualify it is what interviewers are testing when they ask you to "tell the product owner". ## The four things that travel with it 1. **Which problem version.** Exact optimum or acceptable answer? Decide feasibility or find the best? With this clause or without it? The same requirement, minus a single constraint, routinely moves between families, so the verdict must say what it classified. 2. **The evidence tier, with the hedge attached.** There is a real difference between "this is vertex cover with different nouns" and "I have a proof". Say which you have. A proof would embed a known hard problem inside this one; that obligation is real but it is rarely what the moment needs, and pretending to it is worse than the hedge. 3. **The operating envelope.** State n, state the sizes expected, and state where the cost stops being tolerable. A verdict with no numbers cannot be planned against. 4. **The falsifier.** Name what would change the answer: a guaranteed small bound, an input that is always tree-shaped, a relaxation from *best* to *good*. This is also how you invite the one person who knows the domain to hand you the restriction for free. ## Words to avoid, and what to say instead | Tempting phrasing | Why it misleads | Better | |---|---|---| | "It's impossible" | Instances are solved exactly all the time | "Exact answers stop being affordable somewhere above this size" | | "It's proven exponential" | No such proof exists | "No polynomial method is known, and finding one would settle an open question" | | "It's NP so it's slow" | Conflates a class with a cost, and misnames the class | "The exact version is in the hard family; here is what that costs us" | | "We'll just optimise it later" | Treats growth as a constant factor | "Tuning does not change how this grows; the requirement is the lever" | ## What makes the report actionable - Give the **decision** the verdict unblocks. Usually it is one of: accept approximate answers, cap the input, relax a constraint, or buy time with an exact method at the current size. - Give the **cheapest next experiment**: an exact run on representative data to find where the cliff actually sits, which is far more persuasive than a class name. - Give the **requirement question** you want answered: does the business need the optimum, or a defensible answer? In practice this single question resolves more triages than any algorithmic insight. - Record the verdict where the requirement lives, not only in a chat message, so the next person to change the requirement sees why the constraint mattered. ## The reputational cost of overstating Overstating hardness is not a safe error. If you declare a requirement hard and it turns out to be plain pairing, you have spent the team's trust and possibly shipped an approximate answer where an exact one was free. If you understate, you commit a schedule to a search that does not finish. The hedge is what keeps both honest, and it is why the strongest answer to this question in an interview contains the sentence "here is what would change my mind".

  • A stakeholder replies: "then buy a bigger machine". How do you answer?
    Hardware changes the constant, not the growth. Doubling the throughput buys one more unit of input on a doubling curve, so the honest framing is that the lever is the requirement — smaller inputs, a relaxed objective, or acceptance of approximate answers — rather than the budget for compute.
  • What does your report look like when the triage is unresolved rather than hard?
    It says so explicitly, names the clause that blocked the match, states the risk that it turns out to be hard, and proposes the cheapest experiment that would settle it. An unresolved triage that is not reported becomes an optimistic estimate by default.
  • Should the report recommend a coping technique at the same time?
    Name the options briefly, but do not commit. Choosing between an approximation with a guarantee, exploiting a small parameter, or an exact search is a separate decision that depends on what the business needs from the objective, and it deserves its own conversation after the requirement question is answered.

saying these in an interview costs you the question

  • Reports the class name with no input sizes and no assumptions
  • Says impossible when the problem is merely expensive at scale
  • Claims a proof when only a match to a known problem was made
  • Promises that profiling or faster hardware will fix the growth
  • Omits what would overturn the verdict, so nobody can supply it