Are all problems in NP which are not P NP-complete?

Question

1. Are all problems in NP which are not P NP-complete? To make myself more clear, is NP-P=NPC? If not, can you give an example of an NP problem that is neither P nor NP-complete?

2. Are all NP-complete problems NP-hard?

Thank you very much in advance.

Answer 1

First, a picture

1. Problems in NP not known to be in P or NP-complete

It was shown by Ladner that if P ≠ NP then there exist problems in NP that are neither in P nor NP-complete. Such problems are called NP-intermediate problems. The graph isomorphism problem, the discrete logarithm problem and the integer factorization problem are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in P or to be NP-complete.

2. NP-hard is a class of problems which are at least as hard as the hardest problems in NP. Thus, yes, every NP-complete problem is NP-hard.