Problems in NP but not in NPc

Question

Are there currently any known problems that are in NP but are known not to be NP complete?

Answer 1

Yes, many problems known to be NP are thought to be not NP-Complete. These include:

• Any problem in P, other than $\varnothing$ and $\Sigma^*$. (If these problems are NP-Complete, then $\text{P} = \text{NP}$.)

• Any problem known to be in $\text{NP} \cap \text{coNP}$ but not known to be in P, for example, integer factorization (converted to a decision problem). See here.

Problems that are NP, not in P, and not NP-Complete are called "NP-Intermediate", and there is a theorem that says that if $\text{P} \ne \text{NP}$ then such problems exist. See here for a big list of problems expected to be NP-Intermediate.

Additionally, there are two problems that are known to NP and known not to be NP-Complete. These are $\varnothing$ and $\Sigma^*$. The proof is straightforward.