A reviewer rechecks your resolver's chosen version set in a second, yet the resolver ran for hours. Why is that gap expected?

## The asymmetry, precisely A verifier is a function of two things: the instance and **one** proposed answer. Its polynomial bound is a statement about the cost of processing that pair. A solver is a function of one thing: the instance. It must produce an answer that does not exist yet. Those are different jobs with different inputs, and no theorem converts a bound on the first into a bound on the second. Put in the resolver's terms: the reviewer's recheck walks the dependency constraints once and asks, for each, whether the chosen versions satisfy it. The resolver had to **choose** those versions, and the space it chose from is combinatorial. ## Counting what the solver faces - With `n` packages and up to `k` acceptable versions each, the naive space is up to `k^n` combinations. Ten packages with five candidate versions each is already about ten million; twenty packages is about a hundred trillion. - In the general shape of NP, a certificate of `p(n)` bits gives at most `2^p(n)` candidate strings. Multiplying by a polynomial check leaves `2^p(n) * poly(n)` — still exponential. - Constraints prune the space in practice, and good solvers prune aggressively, but pruning is a heuristic on the instance. It is not a bound implied by the verifier's speed. The key move is to notice that the verifier's polynomial is **per candidate**. Nothing in the definition multiplies it by anything smaller than the candidate count. ## What a fast verifier does buy you The gap is not a defect; the checkability is a real asset: - **Decidability with a concrete bound.** Enumerating every certificate and checking it terminates, so a problem in NP is never undecidable and never worse than exponential. - **Auditability.** The answer can be rechecked by a party that does not trust, cannot run, or does not have the solver. Trust moves from the search to the check, and the check is the simple component. - **A cheap correctness oracle for the solver itself.** Any candidate the solver emits can be validated independently, so a bug in the search surfaces as a rejected certificate rather than a silently wrong result. - **Cheap revalidation.** When nothing about the instance changed, rechecking the stored answer is far cheaper than recomputing it. | Intuition | Why it fails | |---|---| | 'Checking is fast, so searching must be nearly as fast' | The check is priced per candidate; the search pays the candidate count too | | 'The checker could be run backwards to produce an answer' | A verifier is a decision procedure over pairs; inverting it is the search problem restated | | 'Hours of runtime means the implementation is poor' | It may be, but the combinatorial space is there regardless of implementation quality | | 'No fast solver is known, so none can exist' | Non-existence is unproved; this is the open question, not a settled result | ## Where this shows up in a plan When someone proposes 'the service will just compute the optimal configuration on each request', the useful response is not 'that is NP-something' as a verdict. It is the split: how large is the candidate space, is a certificate being produced that anyone can recheck, and is an answer that is merely good enough acceptable. The verifier framing gives you a design lever — emit the proof artefact alongside the answer — that is independent of how the search is implemented and survives replacing the solver later. ## The sentence that closes the gap honestly 'Fast to check' and 'fast to find' are related only by a question nobody has answered. Saying 'checking is easy so finding is easy' asserts a resolution to that question; saying 'checking is easy therefore finding is impossible' asserts the opposite one. Both are overclaims. The correct statement is narrow: the verifier bounds the audit, brute force over certificates bounds the search from above, and the distance between those two bounds is open.