Skip to content

Promise-Problem Restriction

Restriction method — instantiates Computability Boundary Mapping

Makes a hard problem solvable by narrowing the inputs the solver is accountable for to those meeting a stated promise, leaving promise-violating inputs as don't-cares.

Promise-Problem Restriction makes a hard problem solvable by narrowing the inputs the solver is held accountable for. Instead of demanding a correct answer on every input, it attaches a promise — a precondition the caller guarantees — and requires correctness only when the promise holds; on promise-violating inputs the solver may do anything at all. The full problem might be undecidable or intractable, but the promised sub-problem can be decidable or efficient, precisely because the solver never has to detect or handle the pathological inputs the promise excludes. Its defining move is a contract on inputs — not on syntax like a fragment, nor on answer quality like an approximation: the domain of responsibility shrinks, and the excluded region becomes officially none of the solver's business.

Example

A numerical service exposes a routine that reports whether a supplied square matrix is invertible and, if so, returns its inverse. Deciding invertibility robustly for arbitrary floating-point matrices is a minefield of near-singular edge cases where tiny rounding differences flip the answer. So the API publishes a promise: inputs are well-conditioned — their condition number is below a stated bound. Under that promise the routine is fast and its verdict is trustworthy; on an ill-conditioned matrix that violates the promise it is explicitly permitted to return anything, and the contract says so in plain sight. Callers who cannot meet the promise must screen their own inputs first. The hard region has not been solved — it has been assigned to the party that can actually discharge it, instead of hidden inside a routine pretending to handle it.

How it works

  • State the promise as a precondition on inputs.
  • Define the problem as a pair — yes-instances and no-instances that need not cover the whole input space; the gap between them is the don't-care region.
  • Build a solver correct on the covered inputs only, free to behave arbitrarily on the rest.
  • Publish the promise so every caller knows the boundary of accountability.

The excluded inputs are not rejected the way an out-of-fragment sentence is — they are simply outside the guarantee, and the solver owes them nothing.

Tuning parameters

  • Promise strength — how much the precondition rules out; a stronger promise makes the solver easier but shifts more screening burden onto callers.
  • Gap width — how far apart the yes- and no-instances must be (the don't-care margin); a wider gap, as in gap/approximation promises, buys tractability at the cost of a fuzzier boundary.
  • Enforcement — whether the promise is checked, assumed, or sampled; checking restores safety but can be as hard as the original problem.
  • Behaviour on violation — truly arbitrary, or a defined safe default; "don't care" is cheapest, a safe default is kinder to callers who slip.

When it helps, and when it misleads

Its strength is isolation: it fences off the genuinely hard region and lets the solver be correct and fast everywhere it promises to work, while being honest about where it does not.

Its danger lives entirely in unpoliced preconditions. If the promise is not enforced and callers violate it, the solver's "anything goes" behaviour produces wrong answers that still look authoritative.[1] The classic misuse is choosing a promise that excludes exactly the inputs that occur in practice, so the guarantee is technically real but vacuous. The discipline is to measure how often real inputs actually satisfy the promise, and to enforce or screen at the boundary rather than trusting callers to have read the contract.

How it implements the components

Promise-Problem Restriction fills the input-scoping side of the archetype — the components a precondition on inputs produces:

  • instance_representation_contract — the promise is a contract on instances: it partitions the input space into promised (must-answer) and don't-care regions, defining which encoded inputs the solver is obligated to handle correctly.
  • scope_boundary — the promise draws the boundary of accountability — the line past which the solver's guarantee, by design, does not extend.

It restricts inputs, not the language — narrowing which sentences can be expressed is Language-Fragment Restriction — and it does not decide what to do with an out-of-scope input at runtime, which is Fallback-Mode Router's dispatch.

Notes

A promise and a language fragment are complementary knobs — you can restrict both the sentences that are expressible and the inputs you answer for. Promise restriction is the one that pairs naturally with a router: because the don't-care region is defined but not policed by the solver itself, the out-of-promise inputs are exactly what a Fallback-Mode Router must catch and re-route, rather than letting them reach a solver that owes them nothing.

References

[1] A promise problem is specified by two disjoint sets — the yes-instances and the no-instances — that need not exhaust the input space; the solver must separate them but may behave arbitrarily on any input in neither set. It is a standard device for isolating a tractable core from an intractable or ill-defined boundary. ↩