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.


LinkBack URL
About LinkBacks
