<p>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 <span class="math-container">$A$</span> that made use of the promise, and let its worst-case running time (on instances where the promise holds) be <span class="math-container">$T(n)$</span>.</p>
<p>Now, for the search problem, you are given an instance where you're not sure whether the promise holds.  No problem.  Run <span class="math-container">$A$</span> on this instance, but terminate it after it executes <span class="math-container">$T(n)$</span> steps.  If <span class="math-container">$A$</span> 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 <span class="math-container">$A$</span>, output that no solution exists.</p>
<p>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 <span class="math-container">$O(T(n)+V(n))$</span>, where <span class="math-container">$V(n)$</span> 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.</p>

CC BY-SA 4.0
2022-09-11T06:02:13.967Z
2022-09-11T06:02:13.967Z
D.W.
<p>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).</p>

CC BY-SA 4.0
2022-09-11T08:42:47.917Z
2022-09-11T08:42:47.917Z
Emil Jeřábek
<p>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).</p>
<p>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?</p>

CC BY-SA 4.0
2022-09-11T11:06:10.460Z
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.
daniel pehoushek
<cc.complexity-theory><ds.algorithms><promise-problems>
Examples of promise search problems that are easier than their non-promise variants?
CSSTUDENT
# Examples of promise search problems that are easier than their non-promise variants?

(Asked by: username_0 on 2022-09-11)

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?

**Tags:** cc.complexity-theory, ds.algorithms, promise-problems

> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_2 on 2022-09-11. Score: 3

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.


---

### Answer by username_3 on 2022-09-11. Score: 1

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).


---

