Diferencia entre revisiones de «NP (clase de complejidad)»
Contenido eliminado Contenido añadido
Sin resumen de edición |
|||
Línea 23:
== Ejemplo: Problema CLIQUE([[Clique]]) ==
Denominamos CLIQUE como en mates discretas, a que materia tan perra no? al siguiente problema:
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 ==
| |||