Reduction Boundary Map¶
Artifact — instantiates Decision-Procedure Boundary Mapping
Locates a new yes/no question by mapping it onto problems whose difficulty is already known — decidable, undecidable, complete-for-a-class, or merely bounded — so you inherit the verdict instead of re-deriving it.
The reduction boundary map is the artifact that answers "how hard is this, really?" by relating a new question to problems whose decidability and cost are already settled. If the question can be transformed into — or shown to contain — a known undecidable problem, it inherits undecidability. If it maps to a known NP-complete problem, it is decidable but likely infeasible at scale. If it reduces to something with a fast algorithm, it is both decidable and cheap. Its defining move is inheritance by reduction: rather than analyzing a procedure from scratch, you borrow the verdict from a problem the field has already classified.
Example¶
A university wants software that answers "can we schedule all final exams into these time slots with no student sitting two exams at once?" Before promising it, an analyst builds a reduction boundary map. The question is recognized as graph coloring in disguise: exams are vertices, a shared student is an edge between two exams, a time slot is a color, and the question becomes "can this graph be colored with k colors?" That lands it squarely in a known class — graph k-colorability is decidable but NP-complete for k ≥ 3.[n1] The map's verdict has two lines that must not be merged: yes/no is always answerable in principle (mark: decidable, not undecidable), but exact answers are infeasible for large instances (mark: feasibility-bounded). So the honest design is an exact solver for small schedules and a bounded or approximate one, with stated limits, for large ones. The map also flags the trap it just avoided: had someone waved the problem off as "just search," they would have promised fast exact answers the problem cannot deliver.
How it works¶
It is a classification artifact built from reductions — not a procedure, and not a spec.
- State the question as a formal problem — what is an instance, and what makes an instance a yes-instance.
- Find candidate known problems it resembles — the catalogue of classified problems is the working material.
- Build or cite an answer-preserving reduction — to a known-hard problem to inherit hardness, or from a known-easy one to inherit an algorithm.
- Read off the verdict — decidable-and-cheap, decidable-but-infeasible, undecidable, or open.
- Keep undecidable and infeasible on separate lines — one means no total procedure ever exists; the other means a procedure exists but its cost is prohibitive, and they route to different fallbacks.
Tuning parameters¶
- Reduction rigor — an informal "this is basically SAT" versus a worked, answer-preserving reduction. Rigor buys certainty about the verdict at the cost of effort.
- Class granularity — coarse (decidable versus not) or fine (P / NP-complete / PSPACE / undecidable). Finer classes give sharper feasibility guidance.
- Direction of reduction — reduce to the new problem to prove it hard, or from an easy problem to inherit a fast method. Different reductions answer different questions.
- Instance-size regime — where the feasibility line is drawn; a problem "infeasible in general" may be perfectly fine at the sizes you actually encounter.
- Approximation openness — whether a bounded or approximate answer counts as acceptable once exact is ruled infeasible.
When it helps, and when it misleads¶
Its strength is saving teams from re-deriving decidability and, more often, from the costlier error of promising fast exact answers to a problem that is decidable but combinatorially hard. Its failure mode is the false or sloppy reduction — mapping to a problem that is only superficially similar, or a transformation that does not actually preserve the yes/no answer, so the inherited verdict is simply wrong. The classic misuse is conflating hard with impossible: treating an NP-complete problem as if it were undecidable and abandoning exact answers that are perfectly reachable at real instance sizes — or the reverse, treating an undecidable problem as merely "slow." The lineage of many-one reduction and completeness[n1] is the discipline here: an inheritance is valid only if the reduction genuinely preserves yes/no answers. The guarding discipline: write the reduction down and check it in the direction you are actually using before trusting the class label, and keep "undecidable" and "infeasible" on separate lines because they route to different fallbacks.
How it implements the components¶
complexity_feasibility_bound— its central output: by locating the question inside a known complexity class it establishes whether an exact procedure is practically feasible, not merely decidable in principle.undecidability_or_open_case_marker— a reduction to a known-undecidable problem marks the question, or a branch of it, as having no total procedure at all — categorically distinct from merely expensive.
It says nothing about the input encoding, the predicate, or the halting proof of an actual procedure — those are the Decision-Procedure Specification and the Termination & Totality Proof Review. And it does not record what happens to the cases it marks open — that ledger is the Fallback Mode Register.
Related¶
- Instantiates: Decision-Procedure Boundary Mapping — the map supplies the feasibility-and-decidability verdict the rest of the mapping hangs on.
- Consumes: Decidability Triage Worksheet — it takes the scoped question the worksheet frames and locates it among known problem classes.
- Sibling mechanisms: Decidability Triage Worksheet · Decision-Procedure Specification · Termination & Totality Proof Review · Fallback Mode Register
Editorial Notes¶
Form Classification¶
Form family: Representation, Specification & Plan
Rationale: Reduction Boundary Map operates by externalizes formal problems and answer-preserving reductions as a classification boundary map. That concrete deployed or enacted form is Representation, Specification & Plan under the frozen taxonomy.
Nearest alternative: Analysis, Modeling & Optimization — Although Analysis, Modeling & Optimization can support this mechanism, the frozen evidence makes its operative form the act that externalizes formal problems and answer-preserving reductions as a classification boundary map; the alternative is therefore secondary rather than defining.
Review outcome: Adjudicated after independent review; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Specialized
Rationale: Mapping problems by reductions, decidability, and complexity completeness is theoretical computer science.
Related originating lineages:
- Mathematics — Logic and computability theory supply undecidability and proof-reduction foundations.
Review resolution: Both blind reviewers agree that computer_science is the primary origin. Explicit reconciliation of encyclopedia synthesis disagreement adopts reviewer_a's classification because mapping problems by reductions, decidability, and complexity completeness is theoretical computer science. The resulting lineage records alternates=mathematics, origin_mode=cross_disciplinary_synthesis, and domain_reach=specialized; these describe formative provenance separately from later applicability.
Encyclopedia synthesis: The exact catalogued form synthesizes established practice rather than reproducing a single standard historical label.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] A many-one reduction transforms every instance of problem A into an instance of problem B so that the yes/no answer is preserved; if B is decidable so is A, and if A is known hard then B is at least as hard. Building on Cook and Levin's proof that Boolean satisfiability is NP-complete, Karp exhibited a web of NP-complete problems — graph coloring among them. NP-complete means decidable but, unless P = NP, with no known efficient exact algorithm — hard, not impossible, and categorically different from undecidable. ↩a ↩b