= Solution
For polynomial-time many-one reductions, an unconditional example is the <empty language>:
$$
\boxed{L=\varnothing\text{ is in NP and is not NP-complete}.}
$$
A procedure that rejects every input decides it in constant time, so it belongs to <P> and hence <NP>. It is not <NP-hard>: the nonempty <formal language> $\{0\}$ belongs to <NP>, but no many-one reduction $f$ can satisfy
$$
0\in\{0\}\quad\Longleftrightarrow\quad f(0)\in\varnothing.
$$
The right-hand side is always false. Thus the hardness condition fails without assuming $\mathsf P\ne\mathsf{NP}$. Giving an ordinary nontrivial problem in <P> would not establish the requested separation unconditionally, because that would require excluding the possibility $\mathsf P=\mathsf{NP}$.
Back to article page
