Todos os problemas NP também são NP-completos?

Question

A definição de NP-completo é

Um problema é NP-completo se

1. pertence à classe NP
2. todos os outros problemas em NP transformam polinomialmente para ele

Então, se todos os outros problemas em NP se transformam em um problema NP-completo, isso também não significa que todos os problemas NP são também NP-completos?Qual é o sentido de classificar os dois se eles são iguais?

Em outras palavras, se temos um problema NP, então por meio de (2) esse problema pode se transformar em um problema NP-completo.Portanto, o problema NP agora é NP-completo e NP= NP-completo.Ambas as classes são equivalentes.

Só estou tentando esclarecer isso para mim.

Answer 1

Não necessariamente.Pode acontecer que NP seja um limite superior conhecido (ou seja, sabemos como resolvê-lo em tempo polinomial não determinístico), mas não um limite inferior conhecido (um algoritmo mais eficiente pode ou não existir).

Um exemplo de tal problema é isomorfismo de gráfico .

Sua frase "se temos um problema NP, então [...] este problema pode se transformar em um problema NP-completo" está incorreta pelo seguinte motivo: qualquer problema em P também está em NP, mas nenhum problema emP é NP-completo (a menos que P= NP, é claro).

Answer 2

Todos os problemas NP também são NP-completos?

Somente se P= NP.

Answer 3

Se o problema A polinomialmente se transforma em problema B, isso não significa necessariamente que o problema B polinomialmente se transforma em problema A.Um problema só pode ser reduzido a um problema de dificuldade igual ou maior.

Se o problema C está em NP, mas não é NP-completo, então ele pode ser polinomialmente transformado em qualquer problema NP-completo, mas isso não é suficiente para torná-lo NP-completo, porque não implica que todos osoutros problemas em NP transformam polinomialmente para o problema C.

Answer 4

Pelo menos deveria ser possível mostrar que vários problemas NP completos também estão em P. Tomemos por exemplo o problema de peneirar números primos ímpares de números ímpares compostos em um conjunto de números ímpares. É possível derivar um método em P para fazer isso. O método de verificação também pode estar em P, conforme discutido no link abaixo.

https://www.academia.edu/s/bcb7736e1e/proof-of-the-p-verses-np-problem-part-two?source=link

Pegue o problema da conjectura de Goldbach, ele pode ser mostrado como NP completo, os primos somando um número par maior que 2 podem ser obtidos em tempo linear. Cada número de Goldbach tem sua própria linha característica com pontos de Goldbach como pontos com coordenadas primos que somam o número de Golbach. Veja o link abaixo para mais informações:

https://www.academia.edu/35904487/Proof_of_the_P_verses_NP_problem-part_one