Isso é possível quando se trata das relações P, NP, NP-Hard e NP-Complete?

7

Eu vi uma imagem que descreve as relações de P, NP, NP-Hard e NP-Complete que se parecem com isso:

https://en.wikipedia.org/wiki/NP-hardness#/media/File:P_np_np-complete_np-hard.svg

insira a descrição da imagem aqui

Gostaria de saber se o seguinte é possível? O que significa, P = NP, mas nem todos eles estão no NP-Hard:

insira a descrição da imagem aqui

Edit: Quero acrescentar: Não estou aqui para dizer se a imagem original está certa ou errada, só estou aqui para fazer uma pergunta se minha imagem contiver uma possível situação. Em outras palavras, é correto assumir que todas as três imagens são possíveis?

Frank
fonte
2
Possível duplicata de If P = NP, por que P = NP = NP-Complete?
Jules Lamur

Respostas:

12

Na verdade, sua versão está correta e a da Wikipedia está errada! (Exceto pelo fato de ter um pequeno aviso na parte inferior.)

E se P=NP, A Wikipedia afirma que todo problema em P é NP-completo. No entanto, isso não é verdade: de fato, todo problema emP seria NP-completo, exceto para os idiomas triviais e Σ.

Você não pode reduzir muitos idiomas não vazios L para , porque uma redução de muitos deve mapear instâncias "yes" de L para "sim" instâncias de , mas  não possui instâncias "yes". Da mesma forma, você não pode reduzir para Σporque não há nada para o qual mapear as instâncias "no". No entanto, seP=NP, então todos os outros idiomas em P é NP-completo, já que você pode resolver o idioma na redução.

Então, apenas para deixar explícito:

  • seu diagrama está correto;
  • A Wikipedia não é (a menos que você leia o pequeno aviso);
  • a área que você rotulou "P, NP"contém os dois idiomas Σ, e nada mais;
  • a área que você rotulou "P, NP-complete "contém todos os outros idiomas em P e nada mais.
David Richerby
fonte
7
"Na verdade, sua versão está correta e a da Wikipedia está errada!" Parece que esse é um julgamento severo sobre a imagem da Wikipedia, com explicações em anexo, enquanto é branda na imagem de quem pergunta . A área rotulada "P, NP" deve ser o círculo completo, assim como a área rotulada "NP-hard" deve significar a área parabólica completa. O rótulo "P, NP-completo" deve ser melhor "NP-completo".
John L.
13
Seria ótimo se você pudesse incluir uma imagem completamente correta, menos suscetível a um entendimento errado.
John L.