# Complexity of $FP^{NP}$

what is the complexity of $FP^{NP}$ w.r.t. $FPSPACE$?

Also can someone please provide a few examples of Problems complete for $FP^{NP}$? If possible let the examples be natural.

1. I don't think it's correct to write "w.r.t. $\mathsf{PSPACE}$" since $\mathsf{PSPACE}$ is a set of decision problems, while $\mathsf{FP^{NP}}$ is a set of functional problems which is contained in $\mathsf{FPSPACE}$. These (which you are interested in) problems can be solved by polynomial amount of queries to $\mathsf{NP}$ oracle (that returns YES/NO answer).

2. A simple example of such problem is:

Given a DNF find an equivalent DNF which has as it's terms only prime (those which cannot be shortened) implicants. It can be solved with linear amount of queries to TAUT/SAT oracle.

• Thank you. will update. I just read TSP is complete for $FP^{NP}$ where as Clique is complete for $FP^{NP[log]}$. When we say TSP or Clique I assume it is finding the size of the TSP and Clique respectively or is it finding the actual TSP or Clique ? Jul 4, 2017 at 11:47
• Well, I think, they are asking for a path/clique itself, not the size/distance, because you can't find a solution knowing only size/distance, but can evaluate size/distance from solution. Jul 4, 2017 at 12:01
• But, I am unable to see how $log$ amount of queries to an $NP$ Oracle can find the clique? The Oracle only gives a boolean answer, and in $#log$ number of $NP$ queries, at best we can decide for only that many nodes in the Graph. Or I missed something ? Jul 4, 2017 at 12:08
• Well, that is already another question. But I'll give you a hint: you can use binary search via oracle. Jul 4, 2017 at 12:11
• I think, Its the value and not the actual clique. Please check out and confirm. sciencedirect.com/science/article/pii/0022000088900396 Jul 4, 2017 at 14:17

Both $\mathrm{FP}$ and $\mathrm{NP}$ are included in polynomial space so $\mathrm{FP^{NP}}$ is, too, since you can simulate the computation and its oracle. Note that, strictly speaking, you need to compare against $\mathrm{FPSPACE}$, since $\mathrm{FP}$ is a set of function problems, whereas $\mathrm{PSPACE}$ is a set of decision problems.

• A follow up Query: The TSP's functional version is complete for $FP^{SAT}[n^{O(1)}]$. And as I understand the $[..]$ represents the number of Queries we are allowed to make to an $NP$ Oracle to solve the problem in polynomial time (by definition of $FP^{SAT}$). But, I am unsure in case of TSP, what the variable $n$ represents? Jul 4, 2017 at 17:42
• @J.Doe That seems strange, as an $\mathrm{FP}$ machine can't possibly make more than polynomially many oracle calls, so it would be weird to state the restriction. But new questions shuold be asked as new questions -- link back to this one if you think the context is needed. Jul 4, 2017 at 17:48
• I am not sure what $n$ is. here is the paper. sciencedirect.com/science/article/pii/0022000088900396. will do. Jul 4, 2017 at 17:53
• @J.Doe You need to ask your new question as a new question. Comments are for pointing out problems with answers and requesting clarifications, not for discussion. Jul 4, 2017 at 17:58