1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Sep 11, 2022 at 11:06

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

The search problem “given a Turing machine that terminates, compute its output” is computable, but it is not computable without the promise (it is as hard as the halting problem).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.