# Are all reductions from NP-complete problems either NP-complete or are contained in P?

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?

• 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. – D.W. Oct 25 at 17:00
• @D.W. Is not $NP$ a subset of $FNP$ where the range is restricted to $\{0,\ 1\}$? – rus9384 Oct 25 at 17:17
• – D.W. Oct 25 at 17:29