skip to content

Your triage calls a scheduling requirement NP-hard; which restrictions hidden in the requirement could pull it back to polynomial time?

level: middleimportance: should knowfreq 46%

answer

  1. hardness is about arbitrary inputs
  2. tree, forest, intervals on a line
  3. two forces, three branches
  4. small value, not small encoding
  5. ask: guaranteed, or true today?

basics

~20 s

Look for structure the general problem lacks: an input shaped as a tree or a line of intervals, two of something where the hard version needs three, or a genuinely small integer bound. Each turns open search into forced or tabulated work.

solid answer

~50 s

Hardness is a claim about the *general* input, and requirements are rarely general. Three restrictions do most of the work. **Input shape**: if the structure is a tree, a forest, or a set of intervals on a line, many problems that are hard on arbitrary graphs become straightforward sweeps or bottom-up computations. **Arity two instead of three**: two literals per clause rather than three, two colours rather than three, pairing rather than grouping into triples — in each case the second choice is forced by the first, which is precisely what kills the search. **A small integer bound**: if capacities or counts are small integers, a table indexed by that value is affordable, though that is polynomial in the *value*, not in the input length. Finding one of these in the requirement is worth more than any clever search.

code

pseudocode · 11 lines
pseudocode
colour[start] = A
push(queue, start)
while queue not empty:
    u = pop(queue)
    for each v adjacent to u:
        if colour[v] is unset:
            colour[v] = other_of(colour[u])   # only one option exists
            push(queue, v)
        else if colour[v] == colour[u]:
            return "no valid two-colouring"
return colour

go deeper

for a junior

Remember that a hardness verdict describes arbitrary inputs. If your data is always a tree, a sorted set of time windows, or a choice between two options, the general result may not be the one that applies.

for a middle

Explain why two options propagate and three branch, and why a small integer bound helps only in proportion to its value rather than to how many digits it takes to write.

for a senior

Show that you convert a relied-upon restriction into a validated precondition with a loud failure, and that you ask whether the restriction is guaranteed by the domain or merely true of current data.

for a principal

Weigh the cost of depending on a restriction against the cost of the general solution, and make sure the dependency is visible to whoever will change the requirement later.

## Hardness is about the general case A classification result says: over *all* inputs of this form, no polynomial method is known. A requirement is never all inputs. It describes the inputs your system will receive, and those usually carry structure the general problem does not have. Triage is therefore not finished at "this is hard" — the second half is reading the requirement again for the restriction that takes it back. ## Restriction one: the shape of the input Many problems that are hard on arbitrary graphs are easy on restricted ones. - **Trees and forests.** With no cycles, a choice at a node can be resolved against its children independently, and a single bottom-up pass settles the whole structure. Choosing a largest conflict-free set of nodes is hard in general and routine on a tree. - **Intervals on a line.** Bookings, shifts and time windows are intervals, and their conflict structure inherits the order of the line. Sorting by endpoint turns "which conflicting things can I choose" into a sweep. - **Bounded degree or local structure.** When each item can interact with only a fixed handful of others, the combinatorial blow-up that makes the general problem hard never materialises. The question to ask the requirement is: *is the graph I am imagining actually arbitrary, or does the domain forbid most of the edges?* ## Restriction two: two rather than three This is the sharpest line in the material, and it is not a matter of degree. | Two | Three | |---|---| | Two literals per clause — satisfiability is decidable in polynomial time | Three literals per clause — NP-complete | | Two colours — a single propagation decides it | Three colours — NP-complete on general graphs | | Pair items one-to-one — bipartite matching is polynomial | Group items into triples — NP-complete | The mechanism behind all three rows is the same: with two options, rejecting one *forces* the other, so a decision propagates and never branches. With three, rejecting one leaves a choice, the propagation becomes a search, and the search is the cost. When a requirement says "each slot takes exactly two people" or "a shift is either day or night", that clause may be carrying the whole plan. ## Restriction three: a genuinely small numeric bound If a capacity, weight or deadline is a small integer, you can build a table indexed by that value and fill it. The subtlety, which interviewers probe: that cost is polynomial in the **value** of the bound, not in the length of the input that encodes it. A capacity written with thirty digits is short to write and enormous to tabulate, so the trick evaporates exactly where the numbers get big. State the bound you are relying on, and guard it. A related but distinct case is a small parameter elsewhere — a fixed number of machines, a team of at most five — where the cost separates into something expensive in the parameter and cheap in the input size. Name that parameter in the plan; choosing the technique that exploits it is the next conversation, not this one. ## How to use this in the room 1. Say the general verdict first, so nobody thinks you missed it. 2. Then list the restrictions you are looking for, in the order above: shape, arity, numeric bound. 3. Ask the requirement's owner whether each restriction is **guaranteed** or merely **true today**. This is the whole point: a restriction you did not ask about is a restriction that will be removed in the next iteration, silently, by someone who does not know it was load-bearing. 4. Record the ones you rely on as explicit preconditions with a guard that fails loudly. The failure mode is symmetric to over-optimism. A candidate who says "NP-hard, so we approximate" without reading for structure throws away an exact answer that was available for free.

  • Why does "two rather than three" change the class so sharply?
    Because two options make every decision deterministic. Rejecting one alternative forces the other, so a single assignment propagates through the whole structure and either completes or contradicts itself. With three, rejecting one still leaves a choice, so propagation turns into branching, and the branching is what the cost is made of.
  • A packing requirement has capacities bounded by a thousand. Is it now a polynomial problem?
    Not in the sense the general result uses. A table indexed by capacity is affordable at a thousand, but that cost is polynomial in the numeric value rather than in the number of bits used to write it. The bound is a precondition you depend on, so guard it rather than treat the hardness as dissolved.
  • How do you protect a plan that depends on the input always being a tree?
    Make the assumption executable. Validate the shape at the boundary, reject or route anything that violates it, and say in the plan what happens if the domain ever allows a cycle. A precondition held only in a design document does not survive contact with a later requirement.

saying these in an interview costs you the question

  • Stops at NP-hard without reading the requirement for structure
  • Assumes a bound that is true today is guaranteed forever
  • Thinks a small numeric bound makes the general problem polynomial
  • Believes two and three are only a difference of degree
  • Applies a tree-shaped method to input that may contain cycles