What three feasibility verdicts can a triage of an unfamiliar task return, and what evidence does each one need?

## The three verdicts Triage is a three-way call made before any code exists, and each verdict carries a different obligation. 1. **Routine.** A polynomial algorithm exists and you can name it, along with the structure it assumes. The evidence is constructive: you can sketch the method and state its bound in terms of the input size n, which you must define — nodes, orders, clauses. 2. **Hard.** The requirement contains a known NP-complete problem. The evidence is a match: the skeleton *is* one of the catalogue entries, or the catalogue entry is a special case of your requirement. The claim this licenses is narrow and must be stated narrowly: no polynomial algorithm is known, and one would resolve a famous open question — not that exponential cost has been proven unavoidable. 3. **Impossible.** The requirement asks, for arbitrary submitted programs or configurations, a non-trivial question about what they *do* when run — whether one ever reaches a forbidden state, whether two always agree, whether any input makes one loop forever. No single program decides such a question for every input. The evidence is the quantifier shape, not a catalogue match. ## What each verdict claims, and what it does not | Verdict | The claim | The frequent misreading | |---|---|---| | Routine | A polynomial method exists for the stated objective on the stated input | "It ran fast on today's data", which is a statement about one instance | | Hard | No polynomial algorithm is known; the worst case grows badly | "Proven exponential", or "cannot be solved" | | Impossible | No program decides it for all inputs | "Too slow to be worth it", which is a cost claim, not an undecidability one | The distance between rows two and three is the one candidates flatten. A hard problem is perfectly solvable — you can compute the exact optimum for a hundred stops and wait. An undecidable one cannot be answered in general at any budget, and the correct response is to renegotiate the requirement into a decidable approximation of it: check a restricted language, answer conservatively, or answer only for bounded runs. ## The evidence you actually cite in a spike - For **routine**: the method's name, the structure it needs (the graph must be acyclic, the intervals must be sorted), and the bound with n defined. - For **hard**: which catalogue problem, and the mapping in one sentence — "every link is an edge, every monitor is a vertex, so this is vertex cover". A full proof embeds the known hard problem inside yours; that is a separate obligation, taken on only if the verdict is disputed. - For **impossible**: the sentence that makes it general — "for any script a customer uploads" — and what happens if you delete the word *any*. - For **unresolved**: what you tried, which clause defeated the match, and what evidence would settle it. ## Why "unresolved" must be said out loud An unfinished triage has a default, and the default is optimism: the work is estimated as if it were routine, because nobody said otherwise. That failure is the expensive one, because it is discovered under real data, after the schedule is committed. Saying "I cannot classify this in the time I had, and here is the clause that blocked me" is a complete answer in an interview and a useful one in a plan. ## Checks before you speak - Define n. "Exponential" in the number of stops and "exponential" in the number of bits of one capacity are different claims. - Check whether the hard clause is the *whole* requirement or a bolted-on extra; dropping one clause often returns the problem to a routine family. - Check the objective: deciding feasibility, finding any solution and finding the *optimal* solution can sit in different classes for the same input. - Check whether exactness was ever required. Much of the time the business asked for "good" and someone wrote "best".