Let's say we have a problem $A \in \mathsf{NP}$. Now let's say we have a reduction $f(\mathsf{SAT}): A \leq \mathsf {SAT}$.

So, assuming that $A$ is not $\mathsf{NP}$-complete we have that $f(\mathsf{SAT})$ is $\mathsf{FNP}$-hard:

  1. $\mathsf{\exists C: \{A \in C \subseteq FNP},\ f(\mathsf{SAT}) \in \mathsf C\}$.
  2. $\mathsf{NP \subseteq C}$.

Since you can use $f(\mathsf{SAT})$ to solve $\mathsf{NP}$-complete problems, $\mathsf C$ can only be $\mathsf{NP}$-hard.

Although assuming that $A$ is $\mathsf{NP}$-complete the reduction is polynomial-time deterministic reduction. I.e. $f(\mathsf{SAT}) \in \mathsf {FP}$.

But what about cases when $f$ is $\mathsf{FNP}$-intermediate? Are they inexistent? For example, if, say, there was a $\mathsf {UP}$ reduction from $\mathsf{SAT}$ to $\mathsf{GI}$, would that mean that $\mathsf{UP=NP}$ is true?

  • 1
    $\begingroup$ What does the notation f(SAT) represent? In what sense is it a FNP problem? The question seems confused about decision problems vs function problems; it has $C \subseteq FNP$ and $NP \subseteq C$, which can't both be right. $\endgroup$ – D.W. Oct 25 '20 at 17:00
  • $\begingroup$ @D.W. Is not $NP$ a subset of $FNP$ where the range is restricted to $\{0,\ 1\}$? $\endgroup$ – rus9384 Oct 25 '20 at 17:17
  • $\begingroup$ en.wikipedia.org/wiki/FNP_(complexity), cstheory.stackexchange.com/q/1088/5038. $\endgroup$ – D.W. Oct 25 '20 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.