# Examples of promise search problems that are easier than their non-promise variants?

By promise search problem, I mean a search problem for which the solution is guaranteed to exist (e.g. find a solution to a linear system of equations, knowing that a solution does exist).

Are there any search problems for which adding this guarantee decreases the complexity of the problem, i.e. the algorithm is able to leverage the promise?

• Given a bit string guaranteed to have a 1, a lookup table can be used to find the first 1. That replaces testing each bit. logn (one memory reference) versus n (bit tests) speedup with the guarantee. Sep 11, 2022 at 11:06

Assuming that you can efficiently verify that any proposed solution is valid, no such problem exists. There's a trivial reduction. Suppose there was an algorithm $$A$$ that made use of the promise, and let its worst-case running time (on instances where the promise holds) be $$T(n)$$.
Now, for the search problem, you are given an instance where you're not sure whether the promise holds. No problem. Run $$A$$ on this instance, but terminate it after it executes $$T(n)$$ steps. If $$A$$ outputs anything, verify that it is a valid solution; if so, output it, and if not, output that no solution exists. If you have to terminate $$A$$, output that no solution exists.
This procedure gives an algorithm for the search problem that is always correct (the proof is by a simple case split on whether the instance has a solution or not), and whose running time is $$O(T(n)+V(n))$$, where $$V(n)$$ is the time to verify a proposed solution. Therefore you can solve the search problem about as fast as you can solve the promise search problem.