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'$?

  • 1
    $\begingroup$ 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. $\endgroup$ – Jake Jun 9 '15 at 15:22
  • $\begingroup$ The correct version adds the requirement that $L,L'$ belong to $\mathsf{NP}$. $\endgroup$ – Yuval Filmus Jun 9 '15 at 15:55
  • $\begingroup$ you are right. I edited my question. $\endgroup$ – TT8 Jun 9 '15 at 16:09
  • $\begingroup$ Think: what can a polynomial-time reduction do? Also, you have to require that $L'\notin \{\Sigma^*,\emptyset\}$, otherwise this is false. $\endgroup$ – Shaull Jun 9 '15 at 16:18
  • $\begingroup$ 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 $\endgroup$ – TT8 Jun 9 '15 at 16:30