GEB

16:28

1

PROGRAMACIÓN II

PROGRAMACIÓN II

Temas  Problemas demostrablemente irresolubles

 Problemas resolubles  Clase P, NP, NP completa y CO-NP

Objetivo Que el estudiante logre entender la clasificación de problemas y su importancia para la Ciencia de la Computación.

16:28

22

PROGRAMACIÓN II

La Teoría de la Computabilidad se ocupa de construir un formalismo matemático para razonar sobre la existencia o no existencia de algoritmos efectivos para problemas particulares.

Uno de los resultados fundamentales de Gödel, Turing y otros lógicos y matemáticos fue el de establecer la división de todos los problemas

matemáticos imaginables en dos clases:

los demostrablemente irresolubles

los resolubles que admiten un algoritmo para su solución

16:28

33

PROGRAMACIÓN II

 Los problemas resolubles admiten un algoritmo para su solución. 

Los algoritmos poseen costos para la resolución del problema.

El área de las ciencias de la computación que se ocupa de determinar los costos (espacio y tiempo) requeridos para la ejecución de un algoritmo es la Teoría de la Complejidad y los resultados que produce son medidas y criterios para determinar la eficiencia de los algoritmos. 16:28

44

PROGRAMACIÓN II

DEMOSTRABLEMENTE IRRESOLUBLES

CLASES

Problema de la detención de la MT Décimo Problema de Hilbert

DEMOSTRABLEMENTE DIFÍCILES (algoritmos ineficientes) RESOLUBLES

Tienen algoritmos eficientes o aún no se ha demostrado su inexistencia

CLASE P Deterministicamente Polinómicos CLASE NP No deterministicamente Polinómicos CLASE NP COMPLETA CLASE CO NP Complementarios de los NP

16:28

55

El problema de parada para máquinas de Turing es el ejemplo de problema irresoluble más conocido. Fue además el primer problema que se demostró

PROGRAMACIÓN II

formalmente que no tenía solución. Sea M una máquina de Turing arbitraria con un alfabeto de entrada Σ. Sea w  Σ*. ¿Puede decidirse si la máquina M parará con la entrada w? Solución: La respuesta a esta pregunta es negativa. No se puede determinar

si una máquina de Turing se detiene con una entrada arbitraria. Relevancia en la Práctica Al ejecutar un programa, este puede terminar después de un número finito de pasos o puede nunca terminar (entrar en un bucle infinito).

16:28

Existe un programa P, tal que, dado un programa cualquiera q y unos datos de entrada x, muestre como salida 1 si q con entrada x termina en un número finito de pasos o muestre como salida 0 si q con x entra a un bucle infinito. Conocer si existe el programa P es, en términos resumidos, el problema de la parada.

77

Hallar un algoritmo para determinar si toda ecuación diofántica (es

PROGRAMACIÓN II

decir, del tipo P(u1, u2, ..., un) = 0 donde P es un polinomio con coeficientes enteros) tiene o no soluciones enteras.

Fue demostrado recursivamente insoluble por Matiyasevich en 1971. Por ejemplo: x2 + y2 - z2 = 0 tiene una solución x=3; y=4;z=5 6x18 - x + 3 = 0 no tiene solución ya que  x: 6x18 > x-3

16:28

88

8

El Instituto Clay de Matemáticas (Cambridge, Massachusetts, EEUU) ha seleccionado siete problemas aún no resueltos, llamados "los siete problemas del milenio"

PROGRAMACIÓN II

P versus NP La conjetura de Hodge

La conjetura de Poincaré La Hipótesis de Riemann El problema de Yang-Mills

El problema de Navier-Stokes La conjetura de Birch y Swinnerton-Dyer 16:28

99

PROGRAMACIÓN II

El objetivo primario del estudio de la complejidad es definir cuáles problemas son tratables y cuáles no, para luego considerar distintos grados de tratabilidad.

Problema

Intratable complejidad exponencial

16:28

Tratable complejidad polinomial

11 11

PROGRAMACIÓN II

Los matemáticos han podido demostrar que:



Para algunos de estos difíciles problemas, nunca podrán

prepararse algoritmos eficientes.



Para muchos de los problemas importantes se tiene únicamente

la sospecha de que será imposible encontrar algoritmos eficientes.

16:28

12 12

PROGRAMACIÓN II

Coloreado de mapas: consiste en determinar si se podrán colorear todos los países del mapa usando un número específico de colores distintos de forma tal que ningún par de países fronterizos tengan el mismo color. En 1975 se demostró que 4 colores bastan para todo mapa. No se dispone de ningún algoritmo eficiente que permita responder si es posible colorear con tres tonos las distintas regiones de un mapa. El coloreado de mapas es un caso particular del coloreado de grafos. Cualquier mapa puede convertirse en un grafo reduciendo cada país a un punto y trazando una línea que una todo par de puntos cuyos países correspondientes tengan frontera común. 16:28

21 21

PROGRAMACIÓN II

La satisfacibilidad proposicional es el problema de determinar si existe una asignación de valores de verdad a los átomos de una fórmula proposicional que la hagan verdadera. El Problema consiste en responder a la pregunta: ¿Existe una

combinación de valores de los elementos de una fórmula proposicional que la hacen verdadera?

Si se tiene k entradas hay 2k posibles alternativas para evaluar, para valores grandes de k el problema se vuelve intratable. 22 16:28 22

PROGRAMACIÓN II

• •

2SAT: resoluble en tiempo polinomial (problema de clase P). Para r>2: son NP-completos (r-SAT: cada cláusula tiene r literales). Todos son equivalentes al 3SAT.

Karp descubrió que muchos problemas importantes de investigación operativa, incluido el colorear un gráfico con tres colores, son también de la misma

dificultad que cualquiera de los problemas que pueden ser asignados a la clase NP, en otras palabras, son NP-completos. Puede demostrarse directamente, trasladando un problema al dominio del otro, que el problema de coloreado del grafo y el problema de satisfactibilidad son equivalentes. Se ha demostrado por métodos similares que varios centenares de problemas, que antes se tuvieron por distintos, son en realidad variantes unos de otros,

cuyas

diferencias son puramente notacionales. Todos estos problemas son

equivalentes al de satisfactibilidad, y son todos, por lo tanto NP-completos. 16:28

23 23



PROGRAMACIÓN II



Muchas veces transformamos un problema en otro. Una reducción es una transformación especial que se utiliza para demostrar la NPCompletitud de un problema. La reducción de problemas es una técnica que permite reducir la solución de un problema a la solución de otro problema cuya solubilidad o insolubilidad ya se conoce.

Si se puede encontrar un algoritmo que solucione un problema P partiendo de la solución de P' , deducimos que: 1- Si P' es soluble, lo es P. 2- Si P es insoluble, lo es P'. Una reducción de un problema P = a un problema P'= es un par de funciones (F1 , F2) tal que: F1 : D  D' F2 : R'  R y (d  D) (r'  R' ): (F1 (d), r' )  q'  (d, F2 (r' ))  q

16:28

24 24

PROBLEMAS DEMOSTRABLEMENTE IRRESOLUBLES Problema de la detención de la MT Décimo problema de Hilbert

PROGRAMACIÓN II

PROBLEMAS DEMOSTRABLEMENTE DIFÍCILES

CLASE NP Completa

Probl. de los números compuestos

CLASE co-NP

16:28

CLASE P

Problema de Euler

Problema de Hamilton Problema SAT Problema de la clique

CLASE NP

26 26

PROGRAMACIÓN II

Problemas  Irresolubles  Resolubles • •

Problemas Demostrablemente difíciles Clase P, NP y NP-Completa

 La importancia de poder demostrar que un problema es NP–completo es que si algún problema NP–completo tuviese un algoritmo que lo resolviese en tiempo polinómico, entonces todos los problemas de la clase NP también lo tendrían.  Por desgracia no se ha podido encontrar hasta ahora tal algoritmo para ningún problema NP–completo.  Aún peor, nadie ha podido demostrar hasta ahora que tal algoritmo no pueda existir.

16:28

Para ser un buen diseñador de algoritmos, se debe entender las base de la teoría de la complititud-NP. Si se da cuenta de que un problema es NP-Completo, entonces, tiene bastante evidencia acerca de la intratabilidad del problema.

27 27