Between P and NP ?

Do any problems exist that aren't NP-complete and not in P?

NP-Intermediate

Given the above diagrams and assuming P≠NP, one may wonder if there are any problems that are in NP but not in NPC or P? Note that we have assumed P≠NP. Problems that exist in this class are called NP-intermediate. Again, very carefully note that NP-intermediate exists only if P≠NP! For the interested, Ladner's theorem proves that if P≠NP then NP-intermediate is non-empty.

Prime Factorization

Prime factorization is suspected to be NP-intermediate problem. Note the use of the ...