# Do all P problems reduce to all NPI problems?

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.

• 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? Apr 21, 2023 at 4:23
• @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$. Apr 21, 2023 at 5:11