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.


2 Answers 2

  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.

  • $\begingroup$ 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 ? $\endgroup$
    – J.Doe
    Jul 4, 2017 at 11:47
  • $\begingroup$ 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. $\endgroup$
    – rus9384
    Jul 4, 2017 at 12:01
  • $\begingroup$ 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 ? $\endgroup$
    – J.Doe
    Jul 4, 2017 at 12:08
  • 1
    $\begingroup$ Well, that is already another question. But I'll give you a hint: you can use binary search via oracle. $\endgroup$
    – rus9384
    Jul 4, 2017 at 12:11
  • $\begingroup$ I think, Its the value and not the actual clique. Please check out and confirm. sciencedirect.com/science/article/pii/0022000088900396 $\endgroup$
    – J.Doe
    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.

  • $\begingroup$ 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? $\endgroup$
    – J.Doe
    Jul 4, 2017 at 17:42
  • $\begingroup$ @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. $\endgroup$ Jul 4, 2017 at 17:48
  • $\begingroup$ I am not sure what $n$ is. here is the paper. sciencedirect.com/science/article/pii/0022000088900396. will do. $\endgroup$
    – J.Doe
    Jul 4, 2017 at 17:53
  • $\begingroup$ @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. $\endgroup$ Jul 4, 2017 at 17:58

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.