¿Qué significa NP-complejo?

Escrito por david dunning | Traducido por ana grasso
  • Comparte
  • Twittea
  • Comparte
  • Pin
  • E-mail
¿Qué significa NP-complejo?
¿Qué significa NP-complejo? (Chad Baker/Ryan McVay/Photodisc/Getty Images)

En la teoría de la complejidad, un problema de decisión es uno cuya salida es "sí" o "no", de otro modo conocido como valor booleano. NP es un juego de problemas de decisión; si la respuesta al problema NP es "sí", hay una prueba de la respuesta que puede ser comprobada en un tiempo razonable, o polinómico.

Otras personas están leyendo

Algoritmos

Un algoritmo es un juego de instrucciones para resolver un problema. Un problema puede ser descrito como NP-complejo si no existe un algoritmo polinómico, o "rápido", para su solución.

Ejemplo

Un ejemplo clásico de un problema NP-complejo es conocido como el problema del "vendedor viajero". Esto requiere la computación de la ruta óptima para que un vendedor viaje a un sinnúmero de destinos diferentes y luego vuelva al punto inicial. Para resolver este problema completamente, incluso para un número reducido de destinos, se requiere más poder de computación del que se encuentra disponible en cualquier computadora moderna.

Características

Un problema de decisión es NP-complejo si un algoritmo de tiempo polinómico para su solución implicase un algoritmo de tiempo complejo para todos los problemas NP. Si un problema NP-complejo puede ser resuelto rápidamente, todos los problemas NP podrían ser resueltos, referenciando a esa única solución especial.

No dejes de ver

Filtrar por:
  • Mostrar todos
  • Artículos
  • Galerías de fotos
  • Videos
Ordenar:
  • Más relevante
  • Más popular
  • Más reciente

No se encuentran artículos disponibles

No se encuentran slideshows disponibles

No se encuentran videos disponibles