0
$\begingroup$

I know that if $P=NP$ then all of the languages in $NP$ are $NP-Complete$, but what about those in $P$?

I assume yes, because $P \subseteq NP$, but I just want to check.

Thanks!

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Both facts are wrong. The empty problem $\emptyset$ (the decision problem whose answer is always false) is in both $\mathsf{P}$ and $\mathsf{NP}$, and is not $\mathsf{NP}$-complete.

See here for some details.

$\endgroup$
1
  • $\begingroup$ You are right, except the trivial ones. $\endgroup$
    – Geo
    Feb 11, 2023 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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