<p>We say that a language <span class="math-container">$X$</span> is polynomial time reducible to <span class="math-container">$Y$</span>, intuitively, if given an algorithm for solving <span class="math-container">$Y$</span>, there's an algorithm for solving <span class="math-container">$X$</span>. 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:</p>
<p><span class="math-container">$f,g$</span> should be polynomial-time computable functions such that <span class="math-container">$(x,w)$</span> is in the NP-Relation for <span class="math-container">$X$</span> if and only if <span class="math-container">$(f(y),g(w))$</span> is in the NP-Relation for <span class="math-container">$Y$</span>.</p>

CC BY-SA 4.0
2024-03-21T10:03:06.960Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2024-03-22T00:09:36.597Z
(i) [Parsimonious reductions](https://en.wikipedia.org/wiki/Parsimonious_reduction) 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.
Neal Young
CC BY-SA 4.0
2024-03-22T00:12:43.987Z
(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$.
Neal Young
CC BY-SA 4.0
2024-03-22T07:57:12.683Z
@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*.
Damiano Mazza
CC BY-SA 4.0
2024-03-22T12:41:52.960Z
@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.
Emil Jeřábek
<cc.complexity-theory><reductions><np>
Reductions That Acts on Witnesses
Boran Erol
# Reductions That Acts on Witnesses

(Asked by: username_0 on 2024-03-21)

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

**Tags:** cc.complexity-theory, reductions, np
> **Comments:**
> **username_1**: 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$.  
> **username_2**: (i) [Parsimonious reductions](https://en.wikipedia.org/wiki/Parsimonious_reduction) 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.  
> **username_2**: (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$.  
> **username_3**: @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*.  
> **username_1**: @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.  

---

## 0 answers

