1
$\begingroup$

It is often said that NP-intermediate problems, such as factoring, graph isomorphism, discrete log, and so on are "harder" than the problems in P. Meaning that they cannot be solved in polynomial time.

But does this imply that all problems in P reduce to all problems in NPI?

This would imply that all problems in P reduce to all problems in NP, because $NP = P \: \cup NPI \: \cup \texttt{NP-complete}$. All problems in P are equivalent (besides the empty and full languages) and all problems in NP reduce to NP-complete problems. So if all problems in P reduce to NPI problems, all problems in P reduce to all NP problems. This doesn't really seem right though.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

If your notion of reduction is polytime m-reduction, then all problems in P (except the empty and full problems) reduce to all problems whatsoever, not just the ones in NP. In particular, any two problems in P are reducible to each other (modulo the previous parenthetical).

Note that I was explicit about the choice of reducibility above. There are of course reducibilities which do distinguish between problems in P (e.g. logtime m-reducibility). However, every notion of reducibility will have its own kind of "minimal complexity" class of problems. Problems in this class will be reducible - in the appropriate sense - to all other problems.

(Very minor terminological annoyance: in computability theory, the term "minimal degree" is used to refer to degrees - i.e. equivalence classes of languages with respect to some appropriate reducibility - which are nonzero and not strictly above any other nonzero degree in the sense of that reducibility. As far as I know this usage doesn't occur in complexity theory, but it's worth warning about.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ That's something I never knew. I have a related question: Is it true that all problems in a complexity class C reduce to all problems in a complexity class $D - C$ (D excluding problems in C) if $C \subset D$ then? $\endgroup$
    – Andrew Baker
    Apr 21 at 4:23
  • 1
    $\begingroup$ @AndrewBaker No. For instance, take $D=\mathsf{EXPTIME}$ and let $C=\mathsf{EXPTIME\setminus\mathsf{P}}$. Here in fact the opposite happens: everything in $D\setminus C$ is reducible to everything in $C$. $\endgroup$
    – Noah Schweber
    Apr 21 at 5:11
  • $\begingroup$ Your caveat for the trivial problems is a bit too early, it should be at the end of that sentence. $\endgroup$
    – Arno
    Apr 21 at 8:02

Your Answer

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

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