<p>It's unclear if <span class="math-container">$L$</span> is a decision problem throughout your question so let's fix some things. Let's denote <span class="math-container">$L$</span> to be your decision problem and let <span class="math-container">$S$</span> be the functional variant.</p>
<p>As Neal mentioned in the comments, your problem (<span class="math-container">$S$</span>) is not a decision problem, so it cannot be in <span class="math-container">${\rm P}^{\rm NP}$</span>. However, it is certainly in <span class="math-container">${\rm FP}^{\rm NP}$</span>.</p>
<p>Consider the <span class="math-container">${\rm NP}$</span> set <span class="math-container">$B= \{ \langle x, i \rangle \mid x \in L $</span> and there is a witness of <span class="math-container">$x \in L$</span> of length <span class="math-container">${\it poly}(|x|)$</span> that has its <span class="math-container">$i$</span>th bit set to <span class="math-container">$1 \}$</span>.</p>
<p>Then you can compute the witness (i.e., solution) in polynomial time relative to <span class="math-container">$B$</span>. (Regarding your linked reference, self-reducibility just restricts the choice of the oracle in this case.)</p>
<p>You can generalize this approach to show that <span class="math-container">${\rm P}^{\rm FNP} \subseteq {\rm P}^{\rm NP}$</span>. In fact, you can show that these are equal, which directly answers your last two questions.</p>

CC BY-SA 4.0
2022-10-03T17:28:59.037Z
2022-10-03T17:28:59.037Z
veryinteresting
<p>One question that recently encountered is the following, suppose I have a task <span class="math-container">$L$</span> which has input length <span class="math-container">$n$</span>, the problem is in the <span class="math-container">$\text{NP}$</span> and I promise that there is a unique solution. (The possible search space is <span class="math-container">$2^{poly(n)}.)$</span></p>
<p>I want to ask what's the complexity of the output of such a solution. Namely, I think this task belongs to the so-called <a href="https://en.wikipedia.org/wiki/FNP_(complexity)" rel="nofollow noreferrer">FNP</a>. Notice that I only have one solution and I promise it has a solution.
I remember that given an NP oracle, I should be able to make a polynomial reduction and claim that I can solve such a problem in <span class="math-container">$P^{NP}.$</span> But it seems it is not the case.
I found the <a href="http://www.cs.toronto.edu/%7Eashe/Search.pdf" rel="nofollow noreferrer">reference</a> claiming that if the problem is NP-complete then it is self-reducible. But I don't know whether is it NP-complete or not.</p>
<p>Finally, I want to ask whether <span class="math-container">$P^{FNP}$</span> is in the <span class="math-container">$PH$</span> (Polynomial hierarchy).
Or in my case, I can say that <span class="math-container">$P^{L}$</span> is in the <span class="math-container">$PH$</span>?</p>
<p>Thanks a lot.</p>

CC BY-SA 4.0
2022-10-01T00:58:58.493Z
Your formulation has two aspects that differ from NP, namely, (i) you guarantee a solution exists and is unique and (ii) the problem, rather than being a decision problem, is to output the solution.  FNP is the variant of NP that just has the second difference (ii).  Regarding the first difference, (i), you may wish to look at results for the UNIQUE-SAT problem, if you haven't already.  I personally don't know of a standard class that combines both these features, but it wouldn't surprise me.   If the class you have in mind is in P, then UNIQUE-SAT is also in P, which is considered unlikely.
Neal Young
<counting-complexity><oracles><polynomial-hierarchy>
Power of unique counting class
En-Jui Kuo
# Power of unique counting class

(Asked by: username_0 on 2022-09-29)

One question that recently encountered is the following, suppose I have a task $L$ which has input length $n$, the problem is in the $\text{NP}$ and I promise that there is a unique solution. (The possible search space is $2^{poly(n)}.)$

I want to ask what's the complexity of the output of such a solution. Namely, I think this task belongs to the so-called [FNP](https://en.wikipedia.org/wiki/FNP_(complexity)). Notice that I only have one solution and I promise it has a solution.
I remember that given an NP oracle, I should be able to make a polynomial reduction and claim that I can solve such a problem in $P^{NP}.$ But it seems it is not the case.
I found the [reference](http://www.cs.toronto.edu/%7Eashe/Search.pdf) claiming that if the problem is NP-complete then it is self-reducible. But I don't know whether is it NP-complete or not.

Finally, I want to ask whether $P^{FNP}$ is in the $PH$ (Polynomial hierarchy).
Or in my case, I can say that $P^{L}$ is in the $PH$?

Thanks a lot.

**Tags:** counting-complexity, oracles, polynomial-hierarchy
> **Comments:**
> **username_1**: Your formulation has two aspects that differ from NP, namely, (i) you guarantee a solution exists and is unique and (ii) the problem, rather than being a decision problem, is to output the solution.  FNP is the variant of NP that just has the second difference (ii).  Regarding the first difference, (i), you may wish to look at results for the UNIQUE-SAT problem, if you haven't already.  I personally don't know of a standard class that combines both these features, but it wouldn't surprise me.   If the class you have in mind is in P, then UNIQUE-SAT is also in P, which is considered unlikely.  

---

## 1 answers

### Answer by username_2 on 2022-10-03. Score: 1

It's unclear if $L$ is a decision problem throughout your question so let's fix some things. Let's denote $L$ to be your decision problem and let $S$ be the functional variant.

As Neal mentioned in the comments, your problem ($S$) is not a decision problem, so it cannot be in ${\rm P}^{\rm NP}$. However, it is certainly in ${\rm FP}^{\rm NP}$.

Consider the ${\rm NP}$ set $B= \{ \langle x, i \rangle \mid x \in L $ and there is a witness of $x \in L$ of length ${\it poly}(|x|)$ that has its $i$th bit set to $1 \}$.

Then you can compute the witness (i.e., solution) in polynomial time relative to $B$. (Regarding your linked reference, self-reducibility just restricts the choice of the oracle in this case.)

You can generalize this approach to show that ${\rm P}^{\rm FNP} \subseteq {\rm P}^{\rm NP}$. In fact, you can show that these are equal, which directly answers your last two questions.


---

