skip to content

A design document calls a shift-assignment feature NP-complete. What two obligations must that claim discharge?

level: middleimportance: must knowfreq 66%

answer

  1. two claims, not one
  2. yes answers need a witness
  3. short certificate, fast check
  4. hardness starts from an existing member
  5. skipping a half renames the claim

basics

~20 s

An NP-completeness claim owes two proofs: membership, that a short certificate for a yes answer is checkable in polynomial time, and hardness, that an already-complete problem reduces into it. Proving only the second gives NP-hardness, not completeness.

solid answer

~40 s

NP-complete is a conjunction, so the document owes two independent arguments. **Membership**: state the feature as a decision problem — "can every shift be covered without breaking a rule?" — and show that a proposed roster is a certificate that is polynomially short and checkable against every rule in polynomial time. **Hardness**: exhibit a polynomial-time reduction that turns instances of a problem already known to be complete for NP into instances of this one, which by transitivity makes every problem in NP reduce into it. A document that only does the second half has proved NP-hardness and should say so. A document that only does the first half has proved the feature is in NP, which on its own justifies nothing about the plan.

code

pseudocode · 16 lines
pseudocode
verify(instance, certificate):
    if length(certificate) > polynomial_bound(size(instance)):
        return false
    if count(certificate) != count(instance.shifts):
        return false
    for each shift in instance.shifts:
        person = certificate[shift]
        if person not in instance.eligible[shift]:
            return false
        for each other in shifts_assigned_to(person, certificate):
            if other != shift and overlaps(shift, other):
                return false
    for each person in instance.staff:
        if total_hours(person, certificate) > instance.hour_cap:
            return false
    return true

go deeper

for a junior

Remember that NP-complete is two claims joined by and, not one word meaning hard. The yes-or-no version of the question is the thing being classified.

for a middle

Be able to state both obligations and say what each looks like concretely: a short certificate with a polynomial-time check, and a polynomial-time transformation from a problem already known to be complete.

for a senior

In review, name which half a document actually proved and ask for the missing one or a weaker word. Watch for certificates that are not polynomially bounded and verifiers that skip a constraint the feature enforces.

for a principal

Decide what standard of evidence a hardness claim must meet before it is allowed to change a roadmap, and make the team state the decision version explicitly so the claim is about the thing being shipped.

## The claim is a conjunction **NP-complete** is not a synonym for slow, exponential, or awkward. It is a two-part status: a problem is NP-complete when it is **in NP** *and* **NP-hard**. A design document that asserts it is making two separate mathematical claims, and a review should be able to point at the argument for each one. Most review disputes about "is this really NP-complete?" are really disputes about which of the two halves was actually shown. ## Obligation one: membership in NP **NP** is a class of *decision problems* — questions whose answer is yes or no. So the first move is to state a decision version of the feature: not "produce the cheapest roster", but "is there a roster covering every shift that breaks no eligibility rule and no hour cap?". Membership then requires exhibiting a **certificate** (a witness) for yes answers with two properties: - its length is bounded by a polynomial in the size of the instance — a full assignment of one staff member per shift qualifies, an enumeration of all candidate rosters does not; - a deterministic **verifier** checks it in time polynomial in the instance size, and the check is *complete*: it tests every rule the feature claims to enforce, not a convenient subset. Nothing is required about *finding* the certificate. That asymmetry is the whole point of the class, and it is why membership is usually the cheap half to prove — but cheap is not free, and it is the half documents skip. ## Obligation two: NP-hardness **NP-hard** means every problem in NP transforms into this one under a polynomial-time reduction. Nobody proves that from scratch. You pick a problem already established as complete for NP, give a polynomial-time transformation that turns its instances into rostering instances preserving the yes/no answer, and let transitivity carry the rest: everything in NP already reduces into the established problem, and reductions compose. The *direction* of that arrow is the classic error and has its own subject; what matters for the claim is that hardness is a statement about **all of NP**, never about the particular instances the feature will receive. ## What each half buys | What was proved | What the document may say | What it may not say | |---|---|---| | Membership only | The problem is in NP; a proposed roster is checkable quickly | That the problem is hard at all | | Hardness only | NP-hard; no polynomial exact algorithm unless P equals NP | That it is in NP, or that it is NP-complete | | Both | NP-complete | That it provably requires exponential time | | Neither, only a slow solver | Our current algorithm is slow | Anything about the problem itself | ## Why membership is the half that gets dropped 1. The engineering consequence everyone cares about — stop demanding a polynomial exact algorithm — rides entirely on hardness, so membership feels ceremonial. 2. The natural phrasing of a scheduling feature is an optimization ("cheapest", "fewest overtime hours"), which is not a decision problem and therefore is not a candidate for membership at all until it is restated. 3. Membership looks obvious, so nobody writes the verifier down — and "obvious" is exactly where an unbounded certificate or an unchecked rule hides. Membership is what places the problem **inside** the catalogue rather than somewhere above it. That matters: a problem can be NP-hard and vastly worse than anything in NP, including undecidable, and a document that skipped membership has not ruled that out. ## What completeness then earns you - **Transitivity.** A complete problem is itself a legitimate starting point for the next hardness proof, because everything in NP reduces into it. - **A precise position.** The problem is a hardest member of NP: no harder than NP (a certificate exists), and no easier than any member. - **A conditional, not a lower bound.** Completeness says a polynomial exact algorithm would put all of NP into P. It does **not** say the problem requires exponential time; that remains open. The practical reading for a review is simple. If the document shows a reduction but no verifier, ask it to change the word to NP-hard or supply the verifier. If it shows a verifier but no reduction, it has proved the feature belongs to the same class as almost every search problem anyone ships, which changes nothing.

  • The document proves hardness by reducing from a problem the author invented last week. What is missing?
    The starting problem has to be one already established as complete for NP. Hardness transfers by transitivity, so if nothing is known about the source, nothing is known about the target either. The reduction may be perfectly correct and still prove nothing.
  • The feature is phrased as "find the cheapest legal roster". Can that phrasing be NP-complete?
    Not as stated: NP is a class of decision problems, and this asks for an object. The usual move is to prove completeness for the decision version — "is there a legal roster of cost at most k?" — and note that the optimization phrasing is NP-hard, since a fast optimizer would answer the decision question.
  • Does membership require that a good roster can be found quickly?
    No. Membership only asks that a roster handed to you can be checked quickly against every rule, and that such a roster is short enough to hand over. Producing it may be as expensive as the problem itself; that gap between checking and finding is what the class is built on.

Certifying a building as the tallest in a city takes two facts: that it stands inside the city, and that nothing in the city is taller. A tower out in the countryside can beat every building in town without being the city's tallest.

saying these in an interview costs you the question

  • Says NP-complete when only a reduction was shown
  • Treats membership as a formality with nothing to prove
  • Offers an exponential brute force as the completeness proof
  • Verifies only some rules and calls that membership
  • Allows an exponentially long certificate and still claims NP