0
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
1
  • 1
    $\begingroup$ +1 (of course if $P=NP$ then $\emptyset$ is $NP$-complete with respect to polytime Turing reductions, but that's a different thing). $\endgroup$ – Noah Schweber Apr 23 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.