22
$\begingroup$

Apparently, if ${\sf P}={\sf NP}$, all languages in ${\sf P}$ except for $\emptyset$ and $\Sigma^*$ would be ${\sf NP}$-complete.

Why these two languages in particular? Can't we reduce any other language in ${\sf P}$ to them by outputting them when accepting or not accepting?

$\endgroup$
1
  • $\begingroup$ Isn’t that NP-complete = NP = P when P = NP? It should be in other class than NP-complete. $\endgroup$
    – YOUSEFY
    May 26, 2021 at 17:05

3 Answers 3

28
$\begingroup$

As there are no strings in $\emptyset$, any machine that computes it always rejects, so we can't map Yes-instance of other problems to anything. Similarly for $\Sigma^{\ast}$ there's nothing to map No-instances to.

$\endgroup$
6
$\begingroup$

You need a polynomial reduction from the problem $A$ to the problem $B$ if you want to prove that $B$ is "harder" than $A$. We build a polynomial reduction by transforming any instance $x$ of $A$ into an instance $f(x)$ of $B$ such that $x∈A$ iff $f(x)∈B$.

The function $f$ must and can be polynomial. If $\mathsf{P}=\mathsf{NP}$ and $A$ is a NP problem, then $f$ can itself solve the problem $A$ of the problem and embed any $x∈A$ into some element $y$ of $B$ and any $x\notin A$ into some element $z$ that is not in $B$.

If $B$ is either $∅$ or $Σ^*$ then $y$ or $z$ cannot exist, otherwise the reasoning above shows that $B$ is harder than $A$.

$\endgroup$
4
$\begingroup$

Just a note: the previous answers are ok, however you're not too far from the correct trivial reduction:

if $\sf{P} = \sf{NP}$ then any $L \in \sf{NP}$ is Karp reducible to the language $\{1\}$ (just map in polynomial time every $x \in L$ to 1, every $x \notin L$ to 0), which is trivially a sparse language

The converse direction: "if an $\sf{NP}$ complete language is Karp reducible to a sparse set then $\sf{P}=\sf{NP}$" is certainly more interesting and it is known as the Mahaney's theorem:

Let $c$ be a constant and $A$ be set such that for all $n$, $A$ has at most $n^c$ strings of length $n$. If $A$ is $\sf{NP}$-complete then $\sf{P}=\sf{NP}$.

$\endgroup$

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.