skip to content

A reviewer calls a shift-assignment problem NP-hard; which problems show that is weaker than NP-complete?

level: middleimportance: must knowfreq 58%

answer

  1. one clause apart
  2. a floor without a ceiling
  3. ask where the certificate is
  4. optimization asks for an object
  5. undecidable can still be hard

basics

~20 s

NP-hard only says everything in NP reduces into the problem; it does not place the problem in NP. Optimization phrasings, which are not decision problems, and the halting problem, which is undecidable, are NP-hard and outside NP.

solid answer

~40 s

The two words differ on one clause. **NP-hard** says every problem in NP reduces into this one under a polynomial-time reduction; it is a lower bound and says nothing about an upper one. **NP-complete** adds that the problem is itself in NP, so a yes answer has a short, fast-checkable certificate. Problems sitting outside NP make the gap visible: an optimization phrasing such as "find the cheapest legal roster" is NP-hard but is not a decision problem at all, so membership does not even typecheck; the halting problem is NP-hard and undecidable, which puts it permanently outside NP; and problems complete for larger classes are NP-hard while nobody believes they are in NP. So "NP-hard" in a design document is a claim about a floor, not a location.

go deeper

for a junior

Hold on to the shape: complete means hard plus a member of NP. Hard on its own is a statement about a floor and leaves the ceiling open.

for a middle

Explain the extra clause and give one concrete problem that is NP-hard and outside NP, such as an optimization phrasing that is not a decision problem at all.

for a senior

Catch the mislabel in a document and say what the correction costs: usually nothing in the engineering conclusion, because the collapse consequence rides on hardness alone.

for a principal

Insist that the decision version be written down, since it is the object being classified, and decide how precise the vocabulary has to be in documents other teams will read and cite.

## Two words, one differing clause The definitions sit one clause apart: - **NP-hard**: every problem in NP reduces into this problem under a polynomial-time reduction. A statement about a **floor** — the problem is at least as hard as everything in NP. - **NP-complete**: NP-hard **and** a member of NP. A floor *and* a **ceiling** — at least as hard as everything in NP, and no harder than the class itself. So NP-complete is the strictly stronger statement, and the extra content is membership: the existence of a polynomially short certificate for yes answers that a deterministic verifier checks in polynomial time. Calling a problem NP-hard when you mean complete loses that ceiling; calling it NP-complete when you have only hardness asserts a ceiling you never proved. ## Three ways to be NP-hard and not in NP **1. It is not a decision problem.** NP is a class of yes/no questions. "Find the cheapest legal roster" asks for an object, so it cannot be a member of NP in the first place, yet it is NP-hard: a fast algorithm for it would answer the decision version "is there a legal roster of cost at most k?" by producing the optimum and comparing. This is the case that shows up most often in a design document, because the feature is naturally phrased as an optimization and the label was borrowed from the decision version. **2. It is undecidable.** The halting problem is NP-hard: for any problem in NP, map an instance to a program that enumerates all candidate certificates and halts exactly when one is accepted — a transformation computable in polynomial time whose output halts precisely on yes instances. Yet the halting problem is undecidable, so no verifier and no algorithm of any running time exists for it. It is definitively outside NP, and it is the cleanest proof that NP-hard imposes no ceiling at all. **3. It is complete for a larger class.** Deciding a fully quantified Boolean formula is complete for PSPACE and therefore NP-hard, and no short certificate is known for it — one would exist only if NP and PSPACE coincided, which nobody expects. Here the honest phrasing is *not believed to be in NP* rather than *not in NP*, because the separation is open. ## The comparison a review needs | | NP-hard | NP-complete | |---|---|---| | Requires a reduction from an already-complete problem | Yes | Yes | | Requires a short, fast-checkable certificate | No | Yes | | Must be a decision problem | No | Yes | | Could be undecidable | Yes | No | | A polynomial algorithm for it would give P equals NP | Yes | Yes | The last row is worth dwelling on: **both** labels carry the collapse consequence, because the collapse rides on the hardness half. That is precisely why the weaker word is still strong enough to justify abandoning a search for an exact polynomial algorithm, and why nobody should feel that hardness alone is a disappointing result. ## Why the sloppy usage costs something - It hides which obligation was actually discharged, so a reader cannot tell whether the document has a verifier or a reduction or both. - It blurs the decision version, and the decision version is the thing the classification is about. A document that never states one has classified nothing. - It suggests a ceiling that may not exist. If the real object is an optimization or a problem complete for a larger class, the team may plan around "as hard as scheduling" when the object in hand is worse. - It breaks the next proof. A complete problem can be reused as the source of a later reduction; a merely hard one cannot serve that role in the same way, because its position inside NP is what makes it a member to reduce *from* while staying in the class. ## How to say it correctly State the decision version. If you proved a reduction only, write **NP-hard**. If you also exhibited a certificate and a verifier, write **NP-complete** and point at both. If the feature that ships is the optimization, say that the decision version is NP-complete and the optimization version is NP-hard — that sentence is precise, short, and survives review.

  • If NP-hard makes no claim about an upper bound, why is it still enough to change a design?
    Because the collapse consequence rides on the hardness half alone: a polynomial exact algorithm for an NP-hard problem would put every NP problem in P. So hardness already justifies dropping the search for a guaranteed-polynomial exact solution, which is usually the decision the document is asking for.
  • Can a problem be in NP and NP-hard without being NP-complete?
    No — that conjunction is the definition of NP-complete, so the three labels cannot come apart that way. What can come apart is NP-hard without membership, and membership without hardness; every problem in P, for instance, is in NP and is not believed to be NP-hard.
  • A document says the optimization version is NP-complete. What is the minimal correction?
    Change it to NP-hard, and add the decision version it was derived from: "is there a legal roster of cost at most k?", which is the object that can be NP-complete. Nothing about the engineering conclusion changes; only the claim becomes one that is true.

saying these in an interview costs you the question

  • Uses NP-hard and NP-complete as interchangeable words
  • Believes every NP-hard problem must lie inside NP
  • Calls an optimization phrasing NP-complete with no decision version
  • Assumes an undecidable problem cannot be NP-hard
  • Thinks NP-hard caps how hard the problem can be