Como provar p= np se problema π ε np-completo e complemento de problema πc ε np?
-
29-09-2020 - |
Pergunta
Como provar se p= np se problema π ε ε np-completo e complemento de problema πc ε np? OU P= np se o NPC intercetir com CO-NPC
Solução
provando $ np= co-np $ não significa necessariamente que $ p= NP $ .Embora, a outra maneira de é correta: Assumir $ p= np $ , então $ co-np= co-p= p= np $ .
Outras dicas
Você não encontrará nada útil com nosso conhecimento atual.No entanto, uma mudança para $ \ pi ^ c \ in \ mbox {p} $ terá você $ \ mbox {p}=mbox {np} $ .
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange