skip to content

A resolver service answers only whether a compatible version set exists. How do you extract an actual set from it in polynomial time?

level: seniorimportance: nice to knowfreq 26%

answer

  1. ask again after each commitment
  2. keep the answer yes at every step
  3. one query per candidate value
  4. the oracle must take amended instances
  5. search reduces to deciding

basics

~20 s

Query it repeatedly on modified instances: pin one package to one version, ask again, keep the pin when the answer stays yes and try the next version otherwise. Polynomially many queries build the whole set.

solid answer

~40 s

Turn the yes/no answer into a search by committing one choice at a time. First confirm the original instance is a yes. Then for the first package, add the constraint 'this package is at version v' and re-ask; if the answer is still yes, keep that constraint permanently and move to the next package, otherwise try the next version. The invariant is that the instance always remains a yes-instance, so some version always survives, and after one pass every package is pinned — which is a full compatible set. With `n` packages and up to `k` versions each, that is at most `n * k` queries. The load-bearing condition is that the service accepts **modified** instances; a black box that answers only the original question gives you exactly one bit and nothing else.

code

pseudocode · 17 lines
pseudocode
build_set(instance, packages):
    if not oracle(instance):
        return NONE                       // no compatible set exists

    chosen = empty map
    for each p in packages:
        pinned = false
        for each v in versions(p):
            trial = instance with constraint (p = v) added
            if oracle(trial):
                instance = trial          // carry the commitment forward
                chosen[p] = v
                pinned = true
                break
        if not pinned:
            return ERROR                  // unreachable: instance is a yes-instance
    return chosen

go deeper

for a junior

Take away the shape only: you can recover a concrete answer from a yes/no service by fixing one choice, asking again, and keeping the choice when the answer stays yes.

for a middle

Explain the query accounting: one query per candidate value per slot, so a polynomial number in total rather than one per combination.

for a senior

State the invariant and the precondition explicitly: the carried instance stays a yes-instance, and the oracle must accept instances with your constraints added.

for a principal

Use it as a leverage argument: a component that only reports feasibility can often be driven to produce an auditable witness, which changes what you can demand of an internal interface.

## The idea: commit a choice, then re-ask This is **self-reducibility**, and it is the reason complexity theory can study yes/no versions of problems without losing the practical question people actually care about. The procedure is mechanical: 1. Ask the oracle about the original instance. If the answer is no, there is nothing to extract; report that and stop. 2. Take the first undecided slot — here, the first package. For each candidate version in turn, form a new instance by **adding the constraint that this package takes that version**, and ask the oracle about the new instance. 3. On the first yes, keep the added constraint permanently: the instance you carry forward now includes it. 4. Repeat for the next slot against the carried-forward instance, until every slot is pinned. The pinned values are the answer. ## Why the invariant holds The loop maintains one property: **the carried instance is always a yes-instance**. It is true at the start by step 1, and each iteration preserves it because a constraint is only kept when the oracle said yes about the instance that includes it. That invariant is what guarantees the inner loop cannot fall through. If the carried instance has a solution, that solution assigns *some* version to the next package, and pinning that version leaves the solution intact, so the oracle must answer yes for at least one candidate. When the loop ends, every slot is pinned and the instance still has a solution — but a fully pinned instance has exactly one candidate assignment left, so the pins themselves are a solution. ## What it costs | Quantity | Value | |---|---| | Slots to decide | `n` packages | | Candidate values per slot | at most `k` versions | | Oracle queries | at most `n * k`, plus one at the start | | Work between queries | building a slightly larger instance, polynomial | So the search costs a polynomial number of decision queries. Contrast that with the `k^n` combinations a blind enumeration faces: the oracle is not being used to test candidate solutions, it is being used to test **commitments**, and each answered commitment removes a whole dimension from the space. ## What the technique requires - **The oracle must accept modified instances.** This is the entire hinge. A service that answers only the fixed original question hands over a single bit; no sequence of repeated calls extracts more. - **Constraints must be expressible in the same problem.** Pinning a package to a version has to yield another legitimate instance of the same decision problem. When the problem's instance format cannot express the commitment, the reduction does not get off the ground. - **It is not a universal law about NP.** Natural problems in the class are typically self-reducible in this style, and for the hardest members of NP the search version is known to reduce to the decision version. It is not known that *every* problem in NP has this property with respect to its own decision version, so state the technique as one that applies where these conditions hold rather than as a theorem about the whole class. ## Why any of this matters Two payoffs, one theoretical and one practical. Theoretically, it is why textbooks and interviewers phrase everything as a decision problem: for the problems people care about, deciding and finding stand or fall together, so nothing is lost by studying the simpler-looking version. Practically, it is a real technique against a component that reports only feasibility: a checker, a constraint engine or a validation endpoint that answers 'satisfiable or not' can be driven into producing a witness, provided you are allowed to hand it amended instances. And once you have the witness, you have the artefact a reviewer can recheck by hand — which is the thing the yes/no answer alone never gave you.

  • What invariant makes the inner loop guaranteed to find a surviving version?
    The carried instance is always a yes-instance. Some solution of it assigns a version to the next package, and pinning exactly that version leaves the solution valid, so the oracle answers yes for at least one candidate. When all slots are pinned, the single remaining assignment is a solution.
  • Why does the technique fail against a service that answers only the original question?
    Because the whole method is repeated querying of amended instances. An oracle fixed to one instance returns one bit, and no number of repetitions adds information. The ability to add a constraint and re-ask is what converts a decision answer into a constructed witness.
  • Is every problem in NP known to be self-reducible in this way?
    No. Natural problems typically are, and for the hardest problems in NP the search version does reduce to the decision version. Whether every problem in the class has this property relative to its own decision version is not known, so it is stated as a technique with conditions rather than a general theorem.

saying these in an interview costs you the question

  • Believes a yes/no oracle can never yield a solution
  • Queries only the original instance and expects a set back
  • Assumes exponentially many oracle calls are needed
  • Drops the committed constraint before the next query
  • Claims the technique works against any oracle whatever it accepts