Assume P=NP. Then every language in P except the empty language and the everything language (sigma*) is NP complete.
Suppose A is in P. I want to reduce any language L in NP to A in polynomial time. I tried to think of a specific language that is NP-complete like SAT, but I couldn't come with an argument. Since L is in P maybe I can come with a polynomial argument that runs A and L and accepts only if they agree.
Dec 7th 2009, 02:02 PM
It seems to me that if you replace all occurrences of NP with P in the original problem, that would also be true. Then the original problem would follow.