Power of unique counting class

Question

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

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