<p>Yes, people have studied this. So-called <span class="math-container">$\gamma$</span>-reductions were introduced by Adleman &amp; Manders. History, further refs, and further developments in <a href="https://doi.org/10.1016/0022-0000(89)90017-2" rel="noreferrer">this paper by Chung &amp; Ravikumar</a>, which also talks about the &quot;strong nondeterministic reductions&quot; introduced by Long.</p>
<p><span class="math-container">$\gamma$</span>-reductions are essentially <span class="math-container">$\mathsf{NPMV}_t$</span> &quot;many-one&quot; reductions, in the sense that there is a nondet polytime machine <span class="math-container">$M$</span> such that, for every input <span class="math-container">$x$</span>, at least one computation path of <span class="math-container">$M(x)$</span> accepts, and  every accepting computation path outputs some <span class="math-container">$y$</span> such that <span class="math-container">$x \in A \Leftrightarrow y \in B$</span>.</p>
<p>Long's strong nondet reductions are the Turing-reduction version of this: there is a nondet oracle TM with a <span class="math-container">$B$</span> oracle such that at least one path of the machine halts, and every halting path gives the correct answer as to whether <span class="math-container">$x$</span> is in <span class="math-container">$A$</span>.</p>
<p>It would also make sense to talk about an <span class="math-container">$\mathsf{NPSV}_t = \mathsf{FP}^{\mathsf{NP} \cap \mathsf{coNP}}$</span> version of <span class="math-container">$\gamma$</span>-reductions - where all accepting computation paths of the reducing machine <span class="math-container">$M$</span> output the same <span class="math-container">$y$</span>. I seem to recall this has been studied as well, but can't find a reference at the moment.</p>
<p>See also:</p>
<ul>
<li><a href="https://doi.org/10.1007/3-540-16761-7_70" rel="noreferrer">https://doi.org/10.1007/3-540-16761-7_70</a></li>
<li><a href="https://doi.org/10.1007/BFb0030320" rel="noreferrer">Nondeterministic logspace reductions</a></li>
</ul>

CC BY-SA 4.0
2024-10-16T21:41:52.740Z
2024-10-16T21:41:52.740Z
Joshua Grochow
<p>Has anyone thought about nondeterministic reductions before? In the sense that the reduction mapping is in <span class="math-container">$\text{FNP}$</span>.
So we say <span class="math-container">$A \le_{FNP} B$</span> if there is a function <span class="math-container">$f \in \text{FNP}$</span> such that <span class="math-container">$x \in A \iff f(x) \in B$</span>.
Informally, one can recognize a proper reduction output in poly-time if it is given, but one cannot necessarily compute the proper reduction output.</p>
<p>We are hoping to use this sort of reduction to prove ''hardness'' for <span class="math-container">$\text{QMA}$</span>.</p>
<p>Does something like this exist and make sense?</p>

CC BY-SA 4.0
2024-10-16T18:15:39.010Z
In your question, is $f$ a proper function in which every input $x$ goes to exactly one output $f(x)$? I think the definitions I can find offhand for $\mathbf{FNP}$ allow more generally for relations which might map an input to many different outputs, or an input to no outputs.
Dylan McKay
CC BY-SA 4.0
2024-10-16T20:53:33.643Z
How bout something like $x \in A \Leftrightarrow \exists w : f(x,w) \in B$.
Reijo Jaakkola
<cc.complexity-theory><complexity-classes><reductions>
nondeterministic reductions?
user68775
# nondeterministic reductions?

(Asked by: username_0 on 2024-10-16)

Has anyone thought about nondeterministic reductions before? In the sense that the reduction mapping is in $\text{FNP}$.
So we say $A \le\_{FNP} B$ if there is a function $f \in \text{FNP}$ such that $x \in A \iff f(x) \in B$.
Informally, one can recognize a proper reduction output in poly-time if it is given, but one cannot necessarily compute the proper reduction output.

We are hoping to use this sort of reduction to prove ''hardness'' for $\text{QMA}$.

Does something like this exist and make sense?

**Tags:** cc.complexity-theory, complexity-classes, reductions

> **Comments:**
> **username_1**: In your question, is $f$ a proper function in which every input $x$ goes to exactly one output $f(x)$? I think the definitions I can find offhand for $\mathbf{FNP}$ allow more generally for relations which might map an input to many different outputs, or an input to no outputs.  
> **username_2**: How bout something like $x \in A \Leftrightarrow \exists w : f(x,w) \in B$.  

---

## 1 answers

### Answer by username_3 on 2024-10-16. Score: 6 | Accepted answer

Yes, people have studied this. So-called $\gamma$-reductions were introduced by Adleman & Manders. History, further refs, and further developments in [this paper by Chung & Ravikumar](https://doi.org/10.1016/0022-0000(89)90017-2), which also talks about the "strong nondeterministic reductions" introduced by Long.

$\gamma$-reductions are essentially $\mathsf{NPMV}\_t$ "many-one" reductions, in the sense that there is a nondet polytime machine $M$ such that, for every input $x$, at least one computation path of $M(x)$ accepts, and every accepting computation path outputs some $y$ such that $x \in A \Leftrightarrow y \in B$.

Long's strong nondet reductions are the Turing-reduction version of this: there is a nondet oracle TM with a $B$ oracle such that at least one path of the machine halts, and every halting path gives the correct answer as to whether $x$ is in $A$.

It would also make sense to talk about an $\mathsf{NPSV}\_t = \mathsf{FP}^{\mathsf{NP} \cap \mathsf{coNP}}$ version of $\gamma$-reductions - where all accepting computation paths of the reducing machine $M$ output the same $y$. I seem to recall this has been studied as well, but can't find a reference at the moment.

See also:

* <https://doi.org/10.1007/3-540-16761-7_70>
* [Nondeterministic logspace reductions](https://doi.org/10.1007/BFb0030320)


---

