Between P and NP ?
Do any problems exist that aren't NP-complete and not in P?
We'll cover the following...
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 ...