2
$\begingroup$

I looked at Sipser ("Introduction to the Theory of Computation"), Problem 7.17:

Prove that if P = NP, then every language in P, except $\emptyset$ and $\Sigma^*$, is NP-Complete.

The solution is as follows:

Let $A$ be any language in NP and let $B$ be another language not equal to $\emptyset$ or $\Sigma^*$. Then there exist strings $x \in B$ and $y \notin B$. To reduce an instance $w$ of $A$ to that of $B$, we just check in polynomial time if $w \in A$. If yes, we output $x$ and $y$ when $w \notin A$.

But I don't see why this reduction could not be applied to any language (except $\emptyset$ and $\Sigma^*$). It would not mean that the language is in P, but the reduction would be correct. The only point where I have doubts is the part where we say that $x$ and $y$ exist, do we somehow have to take into account some computing time for $x$ and $y$ ? Else the reduction would work even for unrecognizable languages for example.

$\endgroup$
  • 2
    $\begingroup$ For a language to be NP-complete, by definition it has to be in NP. $\endgroup$ – Yuval Filmus May 9 at 22:51
  • $\begingroup$ note that each (non-trivial) P language is P-complete. $\endgroup$ – Taylor Huang May 10 at 5:05
  • 1
    $\begingroup$ @TaylorHuang Be careful when using the terminology "P-complete". P-completeness is usually meant regarding log-space (and not poly-time) reductions. $\endgroup$ – dkaeae May 10 at 7:50
  • $\begingroup$ @dkaeae you're right, but I can no longer edit my comment now. I suppose in this context we all agree it shall be regarding poly-time reduction? $\endgroup$ – Taylor Huang May 10 at 10:17
2
$\begingroup$

You are correct. There is no other requirement to the language $B$ other than it is non-trivial (i.e., $x$ and $y$ with said requirements exist). This means that any language in $\mathbf{P}$ (or $\mathbf{NP}$, if you consider $\mathbf{P} = \mathbf{NP}$ as in the exercise's premise) is reducible to a non-trivial language.

Why is this not surprising? The key point here is that we are considering reducibility under poly-time many-one reductions. Since the reductions work in poly-time, they are outright powerful enough to solve the problem which they should be reducing (in your case, the language $A$). Hence, the entirety of the "work" is being done in the reduction itself rather than being transferred to the target which is reduced to (which is the intuitive notion of how a reduction works).

However, this is not in any way a phenomenon exclusively pertinent to $\mathbf{P}$ and poly-time (many-one) reductions. Notice that, for example, if you consider $A \in \mathbf{L}$ (i.e., $A$ is decidable in log-space) and log-space reductions, you will also obtain that $A$ is log-space reducible to any non-trivial language $B$ in the exact same way. In general, if $M$ is some (abstract) machine model which you use for your reductions, then any problems which can be directly decided by $M$ can be reduced to a non-trivial language. The upshot is that reductions are only useful when trying to relate problems which cannot (or you suspect they cannot) be solved directly by the machine model you are using for your reductions.

$\endgroup$
2
$\begingroup$

The reduction does indeed work for any non-trivial language $B$. And that's what the claim you've quoted says: "Let... $B$ be another language not equal to $\emptyset$ or $\Sigma^*$", not "... another NP language..."

So, yes, it could be arbitrarily difficult to compute $x$ and $y$. It might even be impossible to compute them. But that doesn't affect the running time of the reduction because the reduction doesn't have to compute $x$ and $y$. Rather, the person who designs the reduction has to figure out those strings once. If you think in terms of computer programs, the reduction is a program that could be arbitrarily difficult to write but, once it's been written, it runs very quickly. In complexity theory, we don't care how difficult it is to write the program; we only care about how efficiently it runs. If the program exists, we're happy, and these programs certainly exist.

Note that it can still be possible to concretely and explictly write down the reduction, even if $B$ is uncomputable. For example, let $B$ be the language of descriptions of Turing machines that halt on every input. This is highly uncomputable: neither it nor its complement is recursively enumerable, for example, which means that there's no algorithm that can generate all the strings in $B$, or all the strings that are not in $B$. However, we don't need all the strings: we just need two strings. Let $M_1$ be the Turing machine that immediately enters the halt state, regardless of its input, and let $M_2$ be the Turing machine that moves its head to the right forever, regardless of its input. We have $\langle M_1\rangle\in B$ and $\rangle M_2\rangle\notin B$ so, if you cared to figure out the values of $\langle M_1\rangle$ and $\langle M_2\rangle$ as binary strings, you could explicitly write down the reduction from an polynomial-time language to $B$.

$\endgroup$
1
$\begingroup$

If $\mathsf{P}=\mathsf{NP}$ then every nontrivial language is NP-hard, as your argument shows. However, that does not mean that every nontrivial language is NP-complete. For a language to be NP-complete, it needs to be both NP-hard and in NP. Your argument shows that if $\mathsf{P}=\mathsf{NP}$ then a language is NP-complete if and only if it is in P and non-trivial.

$\endgroup$

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.