[Solved]: Having trouble proving a language is NP-complete

Problem Detail: 

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

Asked By : user2977105

Answered By : IABP

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18399