Significats de np-completo en espanyol

Todos los problemas NP-completos se resisten o caen juntos porque un problema NP-completo puede simular cualquier problema NP.

Para dar una idea de este procedimiento, consideremos un típico problema NP-completo: encontrar un ciclo hamiltoniano en una red.

El problema del viajante es "casi" NP-completo, pero hay una cuestión técnica: no se sabe que sea NP.

Pero desde el punto de vista estratégico sugiere que también se puede escoger un problema NP-completo y trabajar con él.

Cualquier problema NP puede convertirse en un caso especial de problema NP-completo "codificándolo", utilizando un código que puede implementarse en tiempo polinómico.

"Si puedes demostrar que un problema es NP-completo, entonces lo que deberías hacer es simplemente dejar de intentar resolverlo", ha explicado.