Skip to content

Questions the library refuses

Some questions a service might be asked have no program that answers them correctly every time, and others have one whose running time explodes as the input grows. A naive service starts searching anyway, holds a worker until a timeout fires, and the client retries into a growing queue. This library instead labels each such question with how hard it is, and for the hardest kinds answers immediately with an explained "no". This page explains those labels in plain words, shows the refusals with real output, and says what your service should do with one.

It is for evaluators and integrators who call the library's helper functions, and for anyone asked "why did it refuse instead of trying?". It assumes nothing beyond knowing that the library makes decisions (see Anatomy of a decision). The calls themselves are described in Use the hardness router.

Two kinds of "no"

The library says "no" in two different places, and they mean different things:

  • A held decision (verdict abstain) comes from decide. The question was answerable, but the evidence was not strong enough to act on automatically. A person should look. See Act, abstain, degrade.
  • A refusal comes from the router, the dispatch function that sits beside decide and answers one-off computational questions (split this graph in two, fingerprint this graph, find the rational roots of this polynomial). A refusal means: "we will not attempt this computation, because no available method could promise an answer within a sensible budget." No person can fix that by looking harder; the question itself has to change.
flowchart TD
    Q["Subgoal: name, hardness label, input"] --> L{"Label is undec,<br/>exptime_trap or fpras?"}
    L -- yes --> R1["Refuse at once<br/>ok=False, nothing runs"]
    L -- no --> N{"Name known?"}
    N -- no --> X["Raise RouterRefuse<br/>(a programming error)"]
    N -- yes --> H["Handler runs"]
    H --> C{"Handler's own check"}
    C -- "WL k above budget" --> R2["Refuse<br/>ok=False, label exptime_trap"]
    C -- "rational roots" --> R3["Refuse<br/>ok=False, label undec"]
    C -- otherwise --> OK["Answer<br/>ok=True, with the label it actually ran under"]

The hardness labels in plain words

Each question sent to the router carries a hardness label (the code calls it an Envelope). The label is the claim you are willing to make about the answer, not the algorithm you wish you had.

Label (Envelope) Plain meaning Everyday example What the router does
p_exact Can be solved exactly, in time that grows reasonably with the input. Colour-refinement fingerprint of a graph (Weisfeiler–Leman with \(k = 1\)). Runs the handler.
fpras Can be estimated by a randomised method to any accuracy you ask for, in reasonable time. Counting the tables with given row and column totals, for an A/B test. Refuses at once (no FPRAS handler is implemented; send the subgoal with its own envelope). No handler exists for this label yet; table sampling lives in compare, outside the router.
ugc_opt A good approximation is cheap, but there is a known best-possible guarantee; searching for a better worst-case method is not worth funding. Max-Cut, vertex cover, k-median facility location. Runs a cheap approximation and reports the reference ratio.
undec No program can answer every instance correctly, or none is known. "Does this polynomial equation have a rational solution?" Refuses at once.
exptime_trap An exact method exists, but its cost explodes as a parameter grows. Weisfeiler–Leman fingerprints with large \(k\). Refuses at once, or the handler refuses when the parameter is over budget.

The labels on ugc_opt deserve care. The Max-Cut ratio 0.8786 is the best any fast algorithm can promise if the Unique Games Conjecture holds (an open conjecture); it is not what the library's spectral method guarantees (that is at least half the edges). The vertex-cover factor 2 is what the maximal-matching method guarantees on any graph; on a two-sided (bipartite) graph an exact answer can be computed quickly (König's theorem), and the method does not do that. The k-median number \(1 + 2/e \approx 1.736\) is a lower bound: no fast algorithm can do better unless P = NP, and no known algorithm achieves it. Never publish it as a ratio you achieve. Details: Approximation limits.

A Module also has an envelope field (default p_exact). It is copied into every decision record as a label; decide does not use it to change any verdict.

Worked examples

A question with no algorithm

uv run grounded-decision examples hilbert_refuse

A computer-algebra service is asked for all rational solutions of \(x^3 + y^3 - 3xyz - 1 = 0\). The caller optimistically labels the request p_exact. The router overrides the label:

  OUTPUT ok=False  envelope=undec
         no complete algorithm for integer polynomials over Q (catalog 004)
         lean=False (a catalog/paper reference, not a Lean kernel check)
  NEXT   return the refusal to the caller; no worker was started

The mathematics: over the whole numbers, no program can decide whether a polynomial equation has a solution (Hilbert's tenth problem, Matiyasevich 1970, a theorem). Over the rationals, the wider literature regards the question as open; this project's math catalog (result 004) claims a negative answer in a manuscript that is not machine-checked (lean=False). Either way, no complete algorithm is available to ship. See Hilbert's tenth problem.

A question whose cost explodes

uv run grounded-decision examples matching_marketplace

A ride-share marketplace fingerprints its driver–rider graph to use as a cache key. Colour refinement (\(k = 1\)) runs; \(k = 5\) is refused:

  OUTPUT wl1 ok=True
         wl5 ok=False  k=5 exceeds cap 2: k-WL takes about n^(k+1) steps, so cost grows exponentially with k (catalog 133)

For a fixed \(k\), the \(k\)-dimensional Weisfeiler–Leman test runs in polynomial time, roughly \(n^{k+1}\) steps for \(n\) vertices, so \(k = 5\) on a large graph is not impossible, just very expensive. The cap Limits.max_wl_k = 2 is a cost budget, and the label exptime_trap means "too expensive under our budget", not a proof that the problem is exponentially hard for fixed \(k\). See Graph fingerprints.

The same example shows the ugc_opt handlers: the spectral Max-Cut cuts all 6 edges of the graph, and the matching-based vertex cover returns 6 participants where 3 (the drivers alone) would do, because the graph is bipartite and the general-graph method is not optimal there.

Every label, called directly

From calling dispatch(Subgoal(name, envelope, payload)) on a 6-cycle graph (the same shape as the marketplace graph), with default Limits:

Subgoal and label sent ok Label returned detail (shortened)
max_cut, ugc_opt True ugc_opt spectral cut with local search 6/6 edges (at least m/2 guaranteed) …
vertex_cover, ugc_opt True ugc_opt maximal-matching cover size 6 (at most 2x optimal); factor 2 is optimal for general graphs only if the Unique Games Conjecture holds, and bipartite graphs can be solved exactly
k_median, ugc_opt True ugc_opt do not claim worst-case factor below 1.7358 (catalog 125)
wl with \(k = 1\), p_exact True p_exact WL-1 colors
wl with \(k = 3\), p_exact False exptime_trap k=3 exceeds cap 2: k-WL takes about n^(k+1) steps, so cost grows exponentially with k (catalog 133)
wl with \(k = 1\), exptime_trap False exptime_trap envelope EXPTIME_TRAP: refuse
rational_zeros, p_exact False undec no complete algorithm for integer polynomials over Q (catalog 004)
vertex_cover, undec False undec envelope UNDEC: refuse
max_cut, fpras False fpras no FPRAS handler is implemented; send the subgoal with its own envelope
vertex_cover, fpras False fpras no FPRAS handler is implemented; send the subgoal with its own envelope
tsp, p_exact raises RouterRefuse unknown subgoal 'tsp'

Notice the rows where the label sent is exptime_trap, undec or fpras: such a request is refused before any handler is looked at, even one that could have answered it under its own label. The router never runs a handler and relabels its answer.

The exact behaviour

dispatch(subgoal, limits=...) returns a RouterResult with fields subgoal, envelope, ok, detail and value:

  1. If the subgoal's label is undec, exptime_trap or fpras: return ok=False with that label. Nothing runs. (For fpras this happens even for a name that is not registered.)
  2. If the name is not registered (available_subgoals() lists them): raise RouterRefuse.
  3. Otherwise run the handler with the Limits you passed. Handlers return the label they actually ran under, which may differ from the one you sent:
  4. rational_zeros always returns ok=False, label undec;
  5. wl returns ok=False, label exptime_trap when \(k > \texttt{max\_wl\_k}\) (default 2);
  6. max_cut, vertex_cover and k_median return label ugc_opt.

Pass the same Limits as your module (dispatch(sg, limits=limits)) so a tenant's budget applies to the router too.

What a refusal does not tell you

  • It is about the kind of question, not your instance. The router refuses every rational_zeros request, including easy ones: a one-variable polynomial's rational roots can be listed with the rational root theorem. If you have an easy special case, solve it yourself, outside the router.
  • exptime_trap is a budget, not a hardness proof for a fixed \(k\). Raising max_wl_k lets larger \(k\) through; note that today any \(k \ge 2\) runs the same pairwise (2-dimensional) procedure, so a higher cap does not buy a stronger fingerprint.
  • ugc_opt numbers are references, not guarantees of the code that ran (see the table on Trust levels and honest limits).
  • A successful answer is not a decision. Router results are not DecisionRecords and go through none of the six checks. If you need both, call dispatch and decide and combine them yourself; see Use the hardness router.

What your service should do when refused

  • ok=False: return a fast, explained error to your caller (for example HTTP 422 with detail in the body). Do not retry: the answer will not change. Log the RouterResult.to_dict() like any other outcome.
  • Offer a smaller question. For undec, offer an explicitly incomplete call ("search rational solutions up to height 1,000; an empty result proves nothing"), labelled as such. For exptime_trap, use \(k \le 2\) and verify any fingerprint match before relying on it, since different graphs can share a fingerprint.
  • RouterRefuse raised: this is a bug in the calling code (an unknown subgoal name, or a label the handler does not accept). Fix the call; do not catch and retry.
  • ugc_opt answers: use them, but publish only the guarantee the method actually has (half the edges for Max-Cut, factor 2 for vertex cover), and compute exact answers yourself where a fast exact method exists (bipartite vertex cover).

Where next