# if P=NP then $L\leq L'$ for all languages [duplicate]

How can I prove that if P=NP then for each non-trivial language $L,L'\in NP$ there exists a polynomial reduction $L\leq L'$?

• I don't really know much about complexity but this sounds wrong to me. Take L to be a polynomial recognizable language and take L' to be an RE-hard language. I don't think, even if P=NP, that there is a polytime reduction from L' to L. – Jake Jun 9 '15 at 15:22
• The correct version adds the requirement that $L,L'$ belong to $\mathsf{NP}$. – Yuval Filmus Jun 9 '15 at 15:55
• you are right. I edited my question. – TT8 Jun 9 '15 at 16:09
• Think: what can a polynomial-time reduction do? Also, you have to require that $L'\notin \{\Sigma^*,\emptyset\}$, otherwise this is false. – Shaull Jun 9 '15 at 16:18
• You can define a reduction to take every x that belongs to L to y that belongs to L' and every x' that does not belong to L to y' that does not belong to L'? @Shaull – TT8 Jun 9 '15 at 16:30