We say that a language $X$ is polynomial time reducible to $Y$, intuitively, if given an algorithm for solving $Y$, there's an algorithm for solving $X$. I know this can be formalized using Karp reductions or Cook reductions. I was wondering if there's a reduction that also acts on witnesses, in the following sense:

$f,g$ should be polynomial-time computable functions such that $(x,w)$ is in the NP-Relation for $X$ if and only if $(f(y),g(w))$ is in the NP-Relation for $Y$.

  • 3
    $\begingroup$ I don’t know what your goal is with these reductions. But there is a standard notion of many-one reductions for NP-search problems where $g$ goes in the opposite direction: a reduction of the search problem associated with $R(x,y)$ to the search problem associated with $S(w,z)$ is a pair of poly-time functions $f$ and $g$ such that $S(f(x),z)\implies R(x,g(x,z))$. This formalizes the idea that if we can efficiently find witnesses for $S$, we can efficiently find fitnesses for $R$ by first applying $f$, then searching for a witness for $S$, and then applying $g$ to get back a witness for $R$. $\endgroup$ Mar 21 at 10:03
  • 2
    $\begingroup$ (i) Parsimonious reductions are similar in spirit to what you have in mind. These are reductions that preserve the number of witnesses. E.g., a reduction from SAT to 3-COLOR so that the number of 3-colorings in the produced instance equals the number of satisfying assignments to the given instance. $\endgroup$
    – Neal Young
    Mar 22 at 0:09
  • $\begingroup$ (ii) I think the (standard) polytime reductions that I know of generally have the property you are asking for. This is usually implicit in the proof.. , which proves that "if $x$ is in $X$ then $f(x)$ is in $Y$", which is the same as "if $x$ has a witness $w$ then $f(x)$ has a witness $g(x, w)$". usually the function $g(x, w)$ is computable in polynomial time. strictly speaking, $g$ is not usually a function of $(x, w)$, not just $w$, but this is sort of a technicality, as $w$ could easily encode $x$. $\endgroup$
    – Neal Young
    Mar 22 at 0:12
  • 1
    $\begingroup$ @EmilJeřábek you need add that $f$ maps "yes" instances to "yes" instances, right? If the OP wants a reference, these reductions are mentioned in Goldreich's "Computational Complexity: a Conceptual Perspective", where he calls them Levin reductions. $\endgroup$ Mar 22 at 7:57
  • 1
    $\begingroup$ @DamianoMazza I guess you are right. I’m used to these reductions in the context of TFNP problems, in which case there are no “no” instances. $\endgroup$ Mar 22 at 12:41


Your Answer

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

Browse other questions tagged or ask your own question.