Diferencia entre revisiones de «NP (clase de complejidad)»
Contenido eliminado Contenido añadido
m BOT - Posible vandalismo de 187.132.170.83, revirtiendo hasta la edición 41109803 de 62.203.117.98. ¿Hubo un error? |
|||
Línea 1:
En [[complejidad computacional|teoría de la complejidad computacional]], '''NP''' es
== La clase NP ==
Línea 23:
== Ejemplo: Problema CLIQUE([[Clique]]) ==
Denominamos CLIQUE
Dado un grafo G y un entero k, ¿es posible encontrar un subgrafo de G completo de tamaño k?
Línea 46:
Ahora deberemos demostrar que G tiene un subgrafo completo de tamaño k ssi es satisfactible. Como todos los miembros del subgrafo pertenecen a cláusulas distintas, cualquier valuación que hace verdadero a todo literal en el subgrafo hace verdadera a la fórmula(recordemos que dos literales complementarios no pueden estar en un subgrafo completo). Si la fórmula es satisfecha, debe existir una valuación que haga verdaderos a al menos un literal en cada cláusula. Sean l1 pertenece a C1, l2 pertenece a C2, . . . , lk pertenece Ck estos literales. Notemos que no es posible que existan dos literales complementarios li y lj. Necesariamente, entonces, podemos construir arcos entre cada par de nodos en donde aparecen dichos literales siguiendo las reglas de construcción del grafo.
== Otros Ejemplos ==
| |||