2
$\begingroup$

Lets assume P = NP, so all problems in NP are decidable in polynomial time, Therefore I can solve all problems in NP in polynomial claiming P = NP = NPC.

But then, how come Σ* belongs to P = NPC because I can't reduce the even length string language (as an example of a language that is not trivial) to Σ*?

one of the steps I made must be incorrect (I sure hope so) please help me find it.

$\endgroup$

1 Answer 1

3
$\begingroup$

No. Even assuming $\mathsf{P}=\mathsf{NP}$, it is not true that all the languages therein are $\mathsf{NP}$-complete.

An example of a language that is in $P$ but it is not $NP$-complete (regardless of the $P$ vs $NP$ matter) is $\Sigma^*$, as you noticed. Indeed, there is no way to reduce any language $L \in \mathsf{NP} \setminus \{ \Sigma^* \}$ to $\Sigma^*$ since, given $x \not\in L$, there is no function $f$ such that $f(x) \not\in \Sigma^*$. A similar argument shows that $\emptyset$ is not $\mathsf{NP}$-complete.

However, if $\mathsf{P}=\mathsf{NP}$, then it is true that all languages in $\mathsf{NP} \setminus \{\emptyset, \Sigma^*\}$ are $\mathsf{NP}$-complete. To see this, let $A \in \mathsf{NP} \setminus \{\emptyset, \Sigma^*\}$ and pick any $L \in \mathsf{NP}$. Since there are $y,z$ such that $y \in A$ and $z \not\in A$, a valid Karp reduction from $L$ to $A$ is the following: $$f(x) = \begin{cases} y & \text{if } x \in L \\ z & \text{if } x \not\in L \end{cases}. $$ Notice that $f$ can be computed in polynomial time since $L \in \mathsf{NP} = \mathsf{P}$ by hypothesis (and hence it is possible to check whether $x \in L$ in polynomial time).

$\endgroup$
1
  • $\begingroup$ thank you very much! clear explanation. $\endgroup$
    – Shy Cohen
    Jun 7 at 14:52

Your Answer

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

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