Problemas NP_completos
Problema de la satisfactibilidad: dada una fórmula lógica, con los operadores, or, and, y not, y una serie de variable lógicas, existe una combinación de valores de las variables que hacen la formula verdadera?
(x1 or x2 or x3) and (x1 or not(x2))
Problemas NP_completos
Si la respuesta a alguno de estos problemas es si ¿se puede probar fácilmente?
“Certificado”
¿De que orden seria un algoritmo de certificado?
Imaginemos una máquina que ante varias alternativas, puede elegir la que quiera, y si una de ellas lleva a la solución de una manera “mágica” elegirá esa. Es una máquina no determinista.
NP conjunto de problemas que se pueden resolver en tiempo polinómico por una máquina no determinista
Reducción
¿A que se refiere el término completo?
O todos los problemas NPC son tratables, o todos son intratables.
El concepto que se usa es la reducción en tiempo polinomial
Dados dos problemas NP_completos una reducción en un tiempo polinomial es un algoritmo que se ejecuta en tiempo polinomial y reduce un problema a otro en el siguiente sentido. Si alguien da una entrada X al primer algoritmo y quiere una respuesta si o no , usamos el algoritmo para transformar X en una entrada Y para el segundo problema, de manera que la respuesta del segundo problema para Y es precisamente la respuesta del primer problema para la entrada X
Reducción del camino Hamiltoniano al problema del Agente
Dado el grafo G, de 5 nodos, tiene un camino Hmiltoniano?
Dado el grafo G’ , tiene el agente un camino de longitud N+1?
La respuesta a la primera pregunta es si, precisamente cuando las respuesta a la segunda es si.
1
2
Reducción
¿Qué indica la transformación anterior?
En términos de tratabilidad el problema del camino Hamiltoniano no es peor que el problema del viajante
¿Cómo demostramos que un nuevo problema esta en NPC?
Reducción
P es el nuevo problema, Q un problema conocido en NPC
Se reduce P a Q, por tanto P no puede ser peor que Q
Reducimos Q a P, por tanto P no puede ser mejor que Q
Si Q es tratable, P es tratable, y si P es tratable, Q es tratable
!!Es necesario un primer problema!!!
Reducción
En 1971 Cook´s demostró que el problema de la satisfacibilidad para el calculo proposicional era NP_completo. Este resultado se conoce como el teorema de Cook´s.
Cook’s se valió de la primera propiedad de los problemas NP-completos, son resolubles por un algoritmo no determinista
Desarrolló una máquina formal, un modelo de computadora de propósito general “Maquina de Turing” dotada con la potencia del no determinismo.
NO COMPUTABILIDAD E INDECIBILIDAD
SubLos problemas que veremos, no tienen solución algorítmica ni con mucho dinero, tiempo o cerebro.
El problema del embaldosado o domino
Tenemos baldosas cuadradas divididas en cuatro por dos diagonales, cada división de un color. Las baldosas tiene una orientación fija
¿Dado un conjunto T de baldosas, se puede embaldosar cualquier área de cualquier tamaño?
El problema del embaldosado o domino
Este tipo de razonamiento no puede ser mecanizado. No existe un algoritmo ni lo habrá para solucionar el problema del embaldosado.
Cualquier algoritmo que podamos diseñar habrá siempre un conjunto de entrada T para el que el algoritmo no termine o de una respuesta errónea
(Gp:) Intratables
(Gp:) Tratables
(Gp:) Indecidibles
Clasificación de los problemas
Un problema algorítmico que no admite algoritmo se llama no computable, si el problema es de decisión se dice que es indecidible
(Gp:) Problemas que no admiten soluciones
(Gp:) Problemas con soluciones razonables
(Gp:) Problemas que no admiten algoritmos razonables
Correspondencia de palabras
Tenemos como entrada dos grupos de palabras de los alfabetos finitos X e Y. El problema pregunta si es posible concatenando palabras de X formar una nueva palabra, Z, tal que concatenando las palabras correspondientes del grupo Y se forme la misma palabra.
Correspondencia 2,1,1,4,1,5
Existe algún algoritmo para resolver e este problema?
El problema es indecidible
Verificación de programas
Nos gustaría obtener un algoritmo que dada la descripción de un problema y un algoritmo, indique si este algoritmo resuelve el problema o no
Queremos que la respuesta sea si, si para cada entrada legal del algoritmo este termina y da la respuesta correcta y no si existen entradas para las que el algoritmo falla o da respuestas erróneas.
Se puede determinar algorítmicamente si dado un problema y un algoritmo el algoritmo resuelve el problema?
Este problema es indecidible
El problema de la parada
El problema tiene dos entradas, el texto de un programa R en un lenguaje L y una entrada para el X. El problema de la parada pregunta si R termina con la entrada X.
(Gp:) Si R(X)¡
(Gp:) Programa
R
(Gp:) Potencial entrada X
(Gp:) Para R con X?
(Gp:) Si R(X) !
(Gp:) si
(Gp:) no
Probando la indecibilidad
Como puedo probar que un problema es indecidible?
La indecibilidad de otro problema se establecerá mostrando la reducción de un problema conocido inecidible al que estamos examinando.
Primero necesito un problema inicial cuya indecibilidad este probada. En este caso es el problema de la Parada.
Probando la indecibilidad
La reducción de un problema P a otro Q no tiene que ser necesariamente limitada; puede tomar cualquier cantidad de tiempo o de espacio. Todo lo que se requiere es una forma algorítmica de transformar una P_entrada en una Q_entrada de manera que la respuesta si/ no de P para una entrada es precisamente la respuesta de Q a la entrada transformada
Si sabemos que P es indecidible Q debe ser también indecidible. La razón es que de otra manera nosotros podríamos resolver P por un algoritmo que tomara cualquier entrada, transfórmala en una entrada para Q y preguntar al algoritmo Q por la respuesta.
Semejante hipotético algoritmo se llama oráculo
Probando la indecibilidad
Asumimos que el problema de la parada es indecidible
< R X>una entrada del problema de la parada, ¿para el programa R con la entrada X?
Transformamos
< P R> entrada del problema de la verificación, P es un problema algorítmico que solo tiene una entrada legal X y su salida no importa. ¿Cuándo es correcto R?
La respuesta del problema de la verificación a la entrada < P R> es si, si y solo si la respuesta del problema de la parada a la entrada < R X> es si. ¿Qué implica esto?
Problemas indecidibles
Como convencerías a alguien que en el problema de la correspondencia de palabras la respuesta es si? y de que un programa para?
Problemas indecidibles tienen certificados finitos
El problema del embaldosado, que certificado tendría?
Problemas indecidibles
Generar y chequear un nuevo certificado C
C no certifica X
Todos los posibles certificados si
Todos los posibles certificados no
Entrada X
SI
NO
Qué ocurre cuando un problema tiene dos certificados?
Problemas menos decidibles
Los problemas con un certificado decimos que son parcialmente decidibles, y son algorítmicamente equivalentes.
¿Se puede reducir el problema de la verificación al problema de la parada?¿Tiene algún certificado?
El problema de la totalidad es menos decidible
Problemas altamente indecidibles. Dominós recurrentes
Niveles de comportamiento algorítmico
Altamente indecidibles
Problemas indecidibles
Problemas intratables
Problemas tratables
 Página anterior | Volver al principio del trabajo | Página siguiente  |