Having trouble proving a language is NP-complete

I'm asked to prove that, if P=NP, that 0*1* is NP-complete, but I'm having trouble going about doing it. I know it's fairly easy to prove it's NP by creating a TM to verify an input (which can be done in O(n) time, and that's polynomial).

But then I now have to reduce an NP-complete problem to 0*1* in order to prove that 0*1* is NP-complete. I'm thinking reducing SAT to it, but I have no idea how to do that, since in SAT all you can use is and, or, and negate, and there's no way to tell if a 1 came before a 0 in an input by doing that (at least, as far as I can tell).

Thanks

• The answer to this problem depends on how you're defining NP completeness. What sort of many-one reductions are you using -- poly-time or log-space? – David Richerby Dec 4 '13 at 9:18

I might be taking this question too lightly, but if you are given that P = NP then showing that 0*1* is in P should satisfy the definition of NP-Complete... i.e if a language L is in P we now know its also in NP (because P=NP is given) and every language in NP is clearly polynomial time reducible to L! Think about it, if A is polynomial time reducible to L and we know L is in P (you'd have to prove this part), then A is also in P...and since P=NP...we know all languages in NP will be polynomial time reducible to L. This satisfies the two conditions of NP-completeness: 1. L is in NP and 2. All A in NP is polynomial time reducible to L

Here is a more technical answer. The "trick" is to put all the work in the reduction function.

Assume $NP = P$, $L \in P$ and let $x_0, x_1$ be two instances, such that $x_1 \in L$ and $x_0 \not\in L$. We have to show that some $NP$-complete problem $Q$ is poly-time reducible to $L$. By assumption, there is an algorithm $M$ deciding $Q$ in polynomial time.

Define a function $$f(x) = \begin{cases} x_1 & \mbox{if M(x) = 1} \\ x_0 & \mbox{else} \end{cases}\mbox{ ,}$$ for all instances $x$ of $Q$. Then clearly $f \in FP$ and $x \in Q \Leftrightarrow f(x) \in L$.

So let $L=\{0^n1^m | n,m \in {\mathbb N} \}$.

As you note, that $L \in P$ is straightforward --- simply make a Turing machine that checks the membership in $L$ in poly time, and this is proven. Since $P \subseteq NP$, this also shows membership in $NP$.

Now you must show hardness. If $P=NP$, then all $P$-hard problems are also $NP$-hard by definition. Thus, to show hardness we need only show that deciding $L$ is $P$-hard. So we reduce a $P$-hard problem to $L$. This is where you run into trouble, because the way you have defined it, $L$ is regular, and therefore requires only log space. I think it may be impossible to prove hardness even with the rather strong assumption that $P=NP$.

• It depends what kind of reductions the asker is using to define NP-completeness. – David Richerby Dec 4 '13 at 9:19