0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Oct 1, 2022 at 0:58

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.