Teoría de Autómatas II

3º cursoIngeniería Técnica en Informática de SistemasUNED

Teoría de Autómatas II 3º Ing. Tec. Informática Sistemas Josep Silva Galiana

Sesión 8

Problemas NP

Teoría de Autómatas II 3º Ing. Tec. Informática Sistemas Josep Silva Galiana

Complejidad de los Problemas

Clase NP:– Lenguajes que pueden aceptar Máquinas de Turing No-

Deterministas en tiempo polinómico Puesto que las MdT deterministas están contenidas en la

clase de las MdT no-deterministas, P NP

Actualmente, no se sabe si P=NP– Tampoco se sabe si aceptar un lenguaje en tiempo

polinómico es equivalente a decidirlo en tiempo polinómico

Teoría de Autómatas II 3º Ing. Tec. Informática Sistemas Josep Silva Galiana

Complejidad de los Problemas

Clase NP:– Existen muchos problemas que se sabe pertenecen a NP

pero no se sabe si pertenecen a P Ejemplo problema viajante de comercio (página 279)

Si alguien demostrara que P=NP– Se tendría “esperanza” en resolver muchos problemas “sin

solución” en tiempo polinómico– El apéndice E muestra muchos problemas de la clase NP

Teoría de Autómatas II 3º Ing. Tec. Informática Sistemas Josep Silva Galiana

Complejidad de los Problemas

Reducciones Polinómicas:– Es una transformación de un lenguaje a otro lenguaje

Dado un lenguaje L1 del alfabeto Σ1 y otro lenguaje L2 del

alfabeto Σ2

Es una función f tal que w є L1 sí y solo sí f(w) є L2 f es computable en tiempo polinómico

“L1 se reduce a L2“ se representa L1 α L2

– Es una herramienta muy útil para clasificar problemas

Teoría de Autómatas II 3º Ing. Tec. Informática Sistemas Josep Silva Galiana

Complejidad de los Problemas

Reducciones Polinómicas:– Si Mf es una reducción polinómica de L1 a L2 y M2 reconoce

L2 entonces:

→ MfM2 reconoce L1

– Teorema 5.3 (página 281)

– Si L1 α L2 y L2 está en P, entonces L1 está en P

– Si L1 α L2 y L1 no está en P, entonces L2 no está en P

Teoría de Autómatas II 3º Ing. Tec. Informática Sistemas Josep Silva Galiana

Complejidad de los Problemas

Preliminares Teorema de Cook:– Cook utilizó el teorema 5.3 para enunciar el famoso

teorema de Cook que permite clasificar lenguajes– Identifica un lenguaje en NP al que cualquier otro lenguaje

en NP se puede reducir Si alguna vez se demuestra que el lenguaje se halla en P,

entonces todos los lenguajes de NP pertenecen a P

– Preliminares– Sea V = {v1, v2, v3} un conjunto de variables booleanas– Asignación de verdad, literal y claúsula

Teoría de Autómatas II 3º Ing. Tec. Informática Sistemas Josep Silva Galiana

Complejidad de los Problemas

Problema de Satisfactibilidad o SAT:– Dado un conjunto finito de variables V y una colección de

cláusulas con respecto a V, ¿existe una asignación de verdad que satisfaga las cláusulas?

– Resolución– Codificar las cláusulas con 0, p y n (página 283) – LSAT: lenguaje consistente en aquellas cadenas que

representan casos de SAT que satisfacen alguna asignación de verdad

Teoría de Autómatas II 3º Ing. Tec. Informática Sistemas Josep Silva Galiana

Complejidad de los Problemas

Problema de Satisfactibilidad o SAT:– EJERCICIO:– Representar las cláusulas:“v1 o ¬v2” “v1 o ¬v2 o ¬v3”“¬v1 o v2 o v3”“¬v1 o v2 o ¬v3 o ¬v4”– (p000/0n00) (p000/0n00/00n0) (n000/0p00/00p0)

(n000/0p00/00n0/000n)– Asignación de verdad: v1, ¬v2, v3, ¬v4 = pnpn– Utilizar algoritmo Figura 5.15 (página 284)

Teoría de Autómatas II 3º Ing. Tec. Informática Sistemas Josep Silva Galiana

Complejidad de los Problemas

Ejercicio 3 (página 291):– A SI– B SI– C NO– D NO

Teoría de Autómatas II 3º Ing. Tec. Informática Sistemas Josep Silva Galiana

Complejidad de los Problemas

Problema de Satisfactibilidad o SAT:– El algoritmo de la Figura 5.15 (página 284) tiene un coste

polinómico en una máquina no-determinista– Pertenece a la clase NP

Teorema de Cook:– Si L es cualquier lenguaje en NP, entonces L α LSAT

– Todos los lenguajes de NP se reducen a LSAT

– Desde el teorema de Cook se han encontrado otros lenguajes con las propiedades de LSAT (NP-completos)

– Leer párrafo final (página 290)