As reviewer of a design that calls shift assignment NP-hard, what evidence do you require before accepting the claim?

## Why a hardness claim deserves review at all A hardness claim is load-bearing: it is normally used to stop an argument, because once a feature is agreed to be NP-hard nobody is expected to keep asking for an exact algorithm with a polynomial guarantee. A claim that strong should be checked as carefully as a capacity estimate, and unlike a capacity estimate it is checkable exactly — the obligations are finite and written down. ## The four checks, in order **1. Which problem version was proved?** NP-hardness and NP-completeness are statements about a specific question. "Shift assignment" is not one. The document must contain a decision version — "is there an assignment covering every shift within the eligibility rules and hour caps?" — and if the shipped feature optimizes something, the relationship between the two must be stated. A document with no decision version anywhere has classified nothing. **2. What did the reduction start from?** Hardness transfers by transitivity, and transitivity carries only what was already there. If the source is a problem the author believes is hard, or a problem from a neighbouring paper whose status is not stated, the proof establishes nothing about NP. The source must be a problem already established as complete for NP. **3. Does the transformation actually hold up?** Two properties, both checkable: it runs in polynomial time in the size of the source instance, and it preserves the answer in **both** directions — every yes maps to a yes, and every produced yes comes from a yes. A transformation that only guarantees one direction is the most common technical defect in an internally written proof. **4. Is the word right?** If nobody exhibited a polynomially short certificate and a polynomial-time verifier, the claim is NP-hard. That is not a lesser result for planning purposes — the consequence about polynomial exact algorithms rides on the hardness half — but the document should say the true thing. ## The scope question, which is where reviews go wrong Hardness is a claim about the general problem over unrestricted inputs. A system receives a particular family of instances, and that family is a different mathematical object. So: - If every instance is bounded — a fixed small staff, a fixed planning horizon — the asymptotic claim does not describe it, and the document should not imply that it does. - If the instances always carry structure the general problem lacks, the general result again does not settle the case; the restricted problem needs its own argument. - Conversely, a proof over a *restricted* family is a stronger result than one over the general problem, and worth noticing when it appears. The right sentence is precise about both objects: the general problem is NP-hard, and here is what our instance family looks like. Combining them into "our scheduling is NP-hard, so it is slow" is the step that a reviewer should not let through. ## A review checklist | Check | Accept when | Reject or downgrade when | |---|---|---| | Decision version | Stated explicitly in the document | Only an optimization phrasing appears | | Source problem | Already established as complete for NP | Unproven, invented, or unstated | | Transformation cost | Polynomial in the source instance size | Cost unstated or instance blows up | | Answer preservation | Holds in both directions, argued | Only one direction is argued | | Membership | Certificate and verifier exhibited | Absent — then the word is NP-hard | | Scope | General claim and instance family kept separate | Asymptotic claim asserted about our inputs | ## What the accepted claim does and does not settle Accepted, the claim settles one thing: there is no exact algorithm with a polynomial guarantee unless P equals NP, so a plan that depends on finding one is not a plan. It does **not** establish a proven exponential lower bound, it does not say today's instances are expensive, and it does not by itself choose what the team builds instead — that decision is a separate discussion with its own evidence. ## The judgment call a lead actually owns The open part is the standard of proof to require, and it is a real trade-off. Demanding a written, checked reduction for every claim is expensive and often unnecessary when the feature is transparently a rephrasing of a catalogued problem. Accepting the label on the strength of resemblance is cheap and occasionally wrong, usually because the feature has a constraint the catalogued problem does not, and that constraint is exactly what makes the real instances tractable. A workable rule: require the full argument when the claim is being used to *stop* work or to justify a large change, and accept a named resemblance plus a stated decision version when it is being used only to set expectations — and in both cases insist that the document says which of the two obligations it actually discharged.