Comment prouver p= np si le problème ε ε np-complet et le problème compléter πc ε np?

Question

Comment prouver si p= np Si le problème π ε ε np-complet et le problème compléter πc ε np? OU ALORS P= np si la NPC se coupe avec co-npc

Answer 1

prouver $ np= co-np $ ne signifie pas nécessairement que $ p= np $ .Bien que l'inverse est correcte: Supposons $ P= NP $ , puis $ CO-NP= CO-P= P= NP $ .

Answer 2

Vous ne trouverez rien d'utile avec nos connaissances actuelles.Cependant, une modification de $ \ pi ^ c \ in \ mbox {p} $ vous obtiendra $ \ m}=mbox {np} $ .