Existence of NP problems with complexity intermediate between P and NP-hard
The result you're describing is called 'Ladner's Theorem.'  The Wikipedia article on 'NP-Intermediate' is probably a good place to start - you can find references to Ladner's original paper there.

There's also an extensive list of such problems on the cstheory Stackexchange.

For a couple of proofs of Ladner's Theorem, check out this note adapted from Downy &amp; Fortnow's paper 'Uniformly Hard Languages'.