Diferencia entre revisiones de «NP-completo»
Contenido eliminado Contenido añadido
Sin resumen de edición |
m Revertidos los cambios de 88.27.244.161 a la última edición de RoyFocker |
||
Línea 1:
En [[complejidad computacional|teoría de la complejidad computacional]], la [[clase de complejidad]] '''NP-completo''' es el subconjunto de los [[problema de decisión|problemas de decisión]] en [[NP (Complejidad computacional)|NP]] tal que todo problema en NP se puede [[Transformación polinómica|reducir]] en cada uno de los problemas de NP-completo
Se puede decir que los problemas de NP-completo son los problemas más difíciles de NP y muy probablemente no formen parte de la clase de complejidad [[tiempo polinómico|P]]. La razón es que de tenerse una solución polinómica para un problema de NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico (y por lo tanto, si se demuestra que para un problema NP-completo no existe solución en tiempo polinómico, ninguno de los problemas NP tendrá solución).
| |||