Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers 3

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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