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 8: | Línea 8: | ||
* (DEF) π є '''NP''' <=> existe una NDTM polinomial que resuelve π (para toda instancia Yπ, alguna de las ramas termina en Qsi en tiempo polinomial) | * (DEF) π є '''NP''' <=> existe una NDTM polinomial que resuelve π (para toda instancia Yπ, alguna de las ramas termina en Qsi en tiempo polinomial) | ||
* (DEF) π є '''co-NP''' <=> π<sup>c</sup> є NP | * (DEF) π є '''co-NP''' <=> π<sup>c</sup> є NP | ||
* (DEF) π' se '''reduce polinomialmente''' a π <=> existe | * (DEF) π' se '''reduce polinomialmente''' a π <=> existe un f:Dπ'->Dπ tq es polinomial y (<math>\forall</math> d є Dπ') d є Yπ' <=> f(d) є Yπ. Se denota '''π' <=p π''' | ||
* (DEF) π є '''NP-Completo''' <=> | * (DEF) π є '''NP-Completo''' <=> | ||
** 1. π є NP | ** 1. π є NP |