# Could the empty language be NP-Complete?

I think the empty language is NP but I'm not sure if it is NP-Complete

You are correct that $$\emptyset\in NP$$, since we already know that $$\emptyset$$ can be decided in constant time (a TM that immediately rejects), and $$DTIME(O(1))\subseteq P\subseteq NP$$.
But $$\emptyset$$ is not NP-complete, regardless of whether $$P=NP$$. Indeed, by definition, a NP-complete language $$A$$ is such that every language $$B \in NP$$ admits a Karp reduction to $$A$$, i.e., a function $$f$$ that is computable in polynomial time and such that $$x \in B \iff f(x) \in A$$.
If $$A= \emptyset$$ and $$B \neq \emptyset$$ then no such function exists, since there is no way to satisfy $$x \in B \implies f(x) \in A$$.
• +1 (of course if $P=NP$ then $\emptyset$ is $NP$-complete with respect to polytime Turing reductions, but that's a different thing). – Noah Schweber Apr 23 at 18:29