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


  • $\begingroup$ 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? $\endgroup$ – 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$.

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

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.