Are there NP problems, not in P and not NP Complete?

Question Detail: 

Are there any known problems in $\mathsf{NP}$ (and not in $\mathsf{P}$) that aren't $\mathsf{NP}$ Complete? My understanding is that there are no currently known problems where this is the case, but it hasn't been ruled out as a possibility.

If there is a problem that is $\mathsf{NP}$ (and not $\mathsf{P}$) but not $\mathsf{NP\text{-}complete}$, would this be a result of no existing isomorphism between instances of that problem and the $\mathsf{NP\text{-}complete}$ set? If this case, how would we know that the $\mathsf{NP}$ problem isn't 'harder' than what we currently identify as the $\mathsf{NP\text{-}complete}$ set?

Asked By : vpiTriumph

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1810

Answered By : Kaveh

Are there any known problems in NP (and not in P) that aren't NP Complete? My understanding is that there are no currently known problems where this is the case, but it hasn't been ruled out as a possibility.

No, this is unknown (with the exception of the trivial languages $\emptyset$ and $\Sigma^*$, these two are not complete because of the definition of many-one reductions, typically these two are ignored when considering many-one reductions). Existence of an $\mathsf{NP}$ problem which is not complete for $\mathsf{NP}$ w.r.t. many-one polynomial time reductions would imply that $\mathsf{P}\neq\mathsf{NP}$ which is not known (although widely believed). If the two classes are different then we know that there are problems in $\mathsf{NP}$ which are not complete for it, take any problem in $\mathsf{P}$.

If there is a problem that is NP (and not P) but not NP Complete, would this be a result of no existing isomorphism between instances of that problem and the NP Complete set?

If the two complexity classes are different then by Ladner's theorem there are problems which are $\mathsf{NP}$-intermediate, i.e. they are between $\mathsf{P}$ and $\mathsf{NP\text{-}complete}$.

If this case, how would we know that the NP problem isn't 'harder' than what we currently identify as the NP Complete set?

They are still polynomial time reducible to $\mathsf{NP\text{-}complete}$ problems so they cannot be harder than $\mathsf{NP\text{-}complete}$ problems.