Trying to prove something in complexity

46 Views Asked by At

I just started to learn about complexity-theory, and I'm trying to prove this:

If P=NP, then every (non-trivial) language in P is NP-complete.

Can someone give me a solution please?

1

There are 1 best solutions below

1
On

A language is $NP$-complete if it is in $NP$ and every $NP$ problem is polynomial time reducible to it. The problems in $NP$-complete are the "hardest" problems in $NP$. So if $NP = P$, then every $NP$ complete problem is in $P$. So $NP$-complete $\subseteq P$.

If $P = NP$, every $NP$-complete problem is in $P$, so in fact $P = NP = NP$-complete.

edit:

If every $NP$-complete problem is actually in $P$, then the hardest problems in $NP$ are all in $P$. This shows that the very hardest $NP$ problems are actually just in $P$ (The "easiest" problems of $NP$). If the hardest problems of $NP$ are in $P$, then any $NP$ problem (hard or not) can be reduced to a problem in $P$. So indeed anything in $NP$ can be reduced in polynomial time to a problem in $P$. Hence $P$ is in $NP$-complete.