# Reductions That Acts on Witnesses

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

• 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$. Mar 21 at 10:03
• (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. Mar 22 at 0:09
• (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$. Mar 22 at 0:12
• @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. Mar 22 at 7:57
• @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. Mar 22 at 12:41