Edición de «Práctica 11: Problemas P y NP (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 13: | Línea 13: | ||
** 2. π є '''NP-Hard''',es decir, (<math>\forall</math> π' є NP) π' <=p π | ** 2. π є '''NP-Hard''',es decir, (<math>\forall</math> π' є NP) π' <=p π | ||
* (TEO) P <math>\subseteq</math> NP y P <math>\subseteq</math> co-NP | * (TEO) P <math>\subseteq</math> NP y P <math>\subseteq</math> co-NP | ||
* (TEO) Si P <math>\cap</math> NP-Completo <math>\neq \empty</math>, o NP-P | * (TEO) Si P <math>\cap</math> NP-Completo <math>\neq \empty</math>, o NP-P <math>\neq \empty</math> -> P=NP | ||
* (TEO) (Cook) SAT es NP-Completo | * (TEO) (Cook) SAT es NP-Completo | ||