Skip to content

Reduction-Direction Checklist

Review checklist — instantiates Computability Boundary Mapping

A pre-flight check that a reduction runs from the known-hard problem into the target — the direction that actually proves hardness — with every assumption named before the verdict is trusted.

Reduction-Direction Checklist is a short review run over a finished reduction before its verdict is believed. Its one job is to catch the single most common and most fatal error in an impossibility or hardness argument: doing the reduction backwards. To prove your target B is hard, you must map a known-hard problem A into B (A ≤ B); mapping B into A shows only that B is no harder than something, which says nothing about B's difficulty. The checklist forces the proof to state out loud which problem is the established-hard source, which is the target, which way the map runs, and what each step assumes — turning a seductive but empty argument into one that either survives the check or is caught before it ships.

Example

In a design review, an engineer argues the team's "policy-consistency" query is intractable and therefore not worth optimising, and shows a reduction: each consistency query is turned into a SAT instance and handed to a SAT solver. The checklist walks the direction. Known-hard problem: SAT. Target: policy-consistency. Direction of the map: policy-consistency → SAT. That is backwards — it shows consistency is at most as hard as SAT, an upper bound, which is the opposite of the claim being made. The review flags it: to argue consistency is hard, you must map SAT into consistency. The team either finds that reverse mapping — and the intractability claim stands — or cannot, and the "not worth optimising" label is withdrawn before it quietly steers the roadmap. Either way a hidden assumption (that SAT-hardness transfers in the drawn direction) is surfaced and settled.

How it works

It is a fixed checklist, not a proof technique — it produces no reduction, only a pass or fail on one someone else built, and it sits downstream of the reduction mechanisms as their gate:

  1. Name the source and confirm its hardness is independently established, not assumed.
  2. Name the target and the exact property being claimed of it.
  3. Confirm the map runs source → target.
  4. Confirm the map is total and computable, and within the claimed resource bound.
  5. Confirm the answer is preserved in the claimed direction.
  6. Register every assumption the argument leans on — the source's status, the encoding's faithfulness, the bound.

Tuning parameters

  • Rigor level — a thirty-second desk check versus a line-by-line audit that re-derives the biconditional; scale it to the stakes of the verdict.
  • Reviewer independence — self-check versus a second person who did not build the proof; independence is what catches the errors the author is blind to.
  • Bound-awareness — whether the check also verifies the resource bound (polynomial-time for a hardness claim) or only computability; needed when the claim is about complexity, not just decidability.
  • Assumption strictness — how aggressively unstated premises must be surfaced and cited rather than waved through.

When it helps, and when it misleads

Its strength is leverage: it is the cheapest possible insurance against the field's most expensive mistake, and it drags the hidden premises of an impossibility claim into the open where they can be challenged.

Its limit is that it checks direction and assumptions only. It will happily pass a correctly-directed reduction whose gadget is subtly wrong, so it is a screen, not a full correctness review, and treating a passed checklist as certifying the whole proof is itself the classic misuse — as is running it to rubber-stamp a conclusion already announced.[1] The discipline is to keep the reviewer independent and to pair the checklist with a complete proof review for any high-stakes verdict.

How it implements the components

Reduction-Direction Checklist fills the review-and-assumption side of the archetype — the components a verification gate produces, not a proof:

  • assumption_register — item six is an assumption register: every premise the reduction leans on (the source's established status, the encoding's faithfulness, the resource bound) is written down and owned rather than left implicit.
  • independent_proof_review — the checklist is a lightweight, independent review gate a reduction must clear before its verdict is trusted, ideally run by someone who did not construct it.

It builds no reduction or preservation contract — those are Many-One Reduction Proof and Turing-Reduction Analysis — and it does not verify a gadget's full correctness, which a complete Proof Checking pass owns.

Notes

The direction error is seductive precisely because the mechanics look identical either way — build a computable map, prove a biconditional — so nothing in the construction itself signals the mistake. Only the roles of source and target differ, and that role-swap is invisible unless someone checks for it explicitly. That is why a dedicated one-item gate pays for itself against a class of error that otherwise slips through every check aimed at the map's internal correctness.

References

[1] The standing convention is "reduce from the hard problem": to show B is hard, exhibit known-hard A ≤ B. Reversing it yields an upper bound on B, not the intended lower bound — the empty argument this checklist exists to catch. ↩