# Are there any algorithms where the recovery of a witness changes the time complexity?

In many algorithms, such as the solution to the longest-subsequence problem using dynamic programming, finding the length of an answer (or signaling the nonexistence of an answer) is easy, but recovering the answer itself (in this case, a substring of the maximum possible length) requires some modifications to the algorithm.

Is there any algorithm where doing so necessitates an increase in the time-complexity of the algorithm?

Note that a change in the big-O complexity of the algorithm as written is enough (for example a change from $O(n)$ to $O(n \ln n)$.

Nontrivial, here, means that the answer should refer to an algorithm which can be modified to return the answer (for example, by storing a table), not a problem for which there is a, say, $O(1)$ algorithm that says if an answer exists and a completely different $O(2^n)$ algorithm that can find the answer.

• There are some trivial examples for problems in which the answer is always YES, for example finding a Nash equilibrium. – Yuval Filmus Dec 17 '14 at 6:35
• There are oracles that only give a YES/NO answer to a problem. To extract a witness, one can use tools from combinatorial group testing, thus increasing the run time. An example of such a problem is the $k$-path problem. – Juho Dec 17 '14 at 8:47
• I'm looking for nontrivial examples. – Soham Chowdhury Dec 17 '14 at 17:27
• One somewhat less trivial example is $n$-puzzle solvability (a generalised version of Sam Loyd's 15-puzzle). Recognising that the puzzle is solvable can be done in $O(n^2 \log n)$ time, by examining the permutation of the pieces and determining whether it is even/odd. However finding the solution is harder, since the solution can have length $\Omega(n^3)$. – Tom van der Zanden Dec 18 '14 at 8:45
• octatoan, 1. I encourage you to use this feedback to improve your question so it will be clearer to others. On this site, we expect you to edit your question so it is clear from just the question -- people shouldn't need to read the comment thread to understand what you are asking or what would qualify as a valid answer. Tell us what you've come up with so far, what seeming answers you've rejected and why, etc. 2. Can you define non-trivial? If you cannot define non-trivial, what is the motivation for your question? What is the context where it arose? – D.W. Dec 19 '14 at 1:52