NP-difícil: diferenças entre revisões

{{Ver desambig| este= a classe de problemas NP-difícil| uma suave introdução| P versus NP}}

 

O sistema de nomeação da família NP é confuso: os problemas NP-difíceis, não são todos NP, a despeito de ter ''NP'' como o prefixo do seu nome da classe. No entanto, os nomes estão agora estabelecidos e improváveis de mudar. Por outro lado, o sistema de nomeação ''NP-'' tem algum sentido mais profundo, porque a família NP é definida em relação à classe NP:

 

; [[NP-completo]]: Estes são os problemas mais difíceis em NP. Tais problemas são NP-difíceis e em NP.

; [[NP-fácil]]: Na maioria tão difíceis quanto NP, mas não necessariamente em NP, uma vez que podem não ser problemas de decisão.