Skip to main content

New answers tagged

2 votes
Accepted

Prove that if P=NP then every two non trivial languages $A,B\in coNP$ holds $A \equiv_{P} B$

We know that if $P=NP$, then we essentially have $P = NP = coNP$ (as you have already demonstrated). Now the problem boils down to showing that any two problems in $P$ are poly-time reducible to each ...
codeR's user avatar
  • 1,760

Top 50 recent answers are included