GEB

09: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.

09: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

09: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. 09: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

09:28

55

PROGRAMACIÓN II

Ciertos problemas son tan difíciles que no existen algoritmos que los resuelvan. Un problema para el que no existirá nunca un algoritmo que lo resuelva es llamado irresoluble o no computable. David Hilbert formula el Entscheidungsproblem o problema de la decisión. La meta de Hilbert era crear un sistema matemático formal "completo" y "consistente", en el que todas las aseveraciones pudieran plantearse con precisión. Su idea era encontrar un algoritmo que determinara la verdad o falsedad de cualquier proposición en el sistema formal.

09:28

Alan Turing (1912-1954)

David Hilbert (1862-1943)

Alan Turing, 1937, publicó un trabajo sobre números calculables que puede considerarse en parte como el origen de la Informática Teórica. Introdujo la máquina de Turing (MT) como un modelo matemático abstracto que permitió formalizar el concepto de algoritmo. 66

6

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).

09: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

09: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 09:28

99

PROBLEMAS DEMOSTRABLEMENTE IRRESOLUBLES

PROGRAMACIÓN II

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

PROBLEMAS DEMOSTRABLEMENTE DIFÍCILES

PROBLEMAS RESOLUBLES

En principio, siempre es posible resolverlos, pero para los cuales, sólo se conocen algoritmos ineficientes (y, por consiguiente, la mayoría de las veces, intratables).

09:28

10 10

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

09: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.

09:28

12 12

PROGRAMACIÓN II

La CLASE P está constituida por algoritmos de tiempo polinómico. Para que un problema sea asignado a la clase P ningún caso particular del problema puede exigir para su resolución un tiempo mayor que el polinómico.

El método de solución es determinístico en el sentido de que garantiza la existencia de una solución, y ello en un tiempo inferior al de una cierta potencia fija del tamaño N del problema.

09:28

13 13

CLASE NP significa “No determinísticamente polinómicos”.

PROGRAMACIÓN II

La CLASE NP incluye a todos los problemas de la clase P, luego P es un subconjunto de NP.

La clase NP contiene otros problemas de status menos seguro. Todos ellos son problemas resolubles al menos en teoría; aunque por el momento solamente se conocen algoritmos de tiempo exponencial. La clase NP corresponde a la clase de problemas cuya solución puede ser verificada en tiempo polinomial. Por ejemplo: Consideremos el problema del camino Hamiltoniano: Un camino Hamiltoneano es un camino que pase una vez y solamente una vez por todos los puntos (nodos) de un grafo.

¿Tiene un grafo G un ciclo Hamiltoniano? Un posible candidato para este problema puede ser verificado en tiempo polinomial, luego este problema está en la categoría NP. 09:28

14 14

14

La CLASE NP completa, es un subconjunto de la clase NP compuesta PROGRAMACIÓN II

con los problemas que tienen la siguiente propiedad: "si uno de ellos pudiera resolverse mediante un algoritmo eficiente, entonces todos los demás problemas de la clase NP podrían resolverse eficientemente".

Es decir, todo otro miembro de la clase puede ser eficientemente reducido a uno de ellos.

09:28

15 15

15

PROGRAMACIÓN II

Stephen Cook, en 1971, formuló el Problema "P versus NP" y se lo considera el problema central de las Ciencias de la Computación. Se conjetura que "P = NP", pero nadie lo ha podido demostrar. Técnicamente, P denota a la clase de los algoritmos que utilizan tiempo polinómico, mientras NP denota a la clase de los algoritmos no determinísticos que emplean tiempo polinómico. La importancia de la pregunta P = NP radica en que de encontrarse un algoritmo en P para un problema NP-completo, todos los problemas NP-completos (y por ende, todos los problemas de NP) tendrían soluciones en tiempo polinómico. 09:28

16 16

16

PROGRAMACIÓN II

Recorrer los 7 puentes pasando por cada uno de ellos una y solamente una vez.

A

a

g

C

c

d

C

e

D

c

d

e

A B

f b

g

a

b

D

f

B 09:28

17 17

Averiguar si existe un cierto camino que pase exactamente una vez por cada línea. C PROGRAMACIÓN II

El grafo debe cumplir dos condiciones: 1. Ser conexo. 2. En todos los nodos (con la posible excepción de 2) debe haber un número par de líneas.

c

d

e

A a

El problema de los puentes no tiene caminos eulerianos (cumple la primera pero no la segunda condición)

g

b

D

f

B

Este algoritmo tiene un tiempo de ejecución O(n) es decir pertenece a la Clase P 09:28

18 18

Determinar si existe un camino que pase una vez y solamente una vez por todos los puntos (nodos) de un grafo.

PROGRAMACIÓN II

No se descubrió un algoritmo eficiente para este problema. El problema de los puentes de Könisberg sí tienen recorrido hamiltoniano. C

c

C

d

g e

A a

b

f

g

c

D

D A b

B

B

Este problema pertenece a la Clase NP completa 09:28

19 19

19

PROGRAMACIÓN II

Problema de emparejamiento: consiste en asignar habitaciones a estudiantes compatibles (según hábitos, gustos, etc.). El conjunto de estudiantes se representan por puntos en un grafo y cada par de estudiantes que puedan compartir la habitación por una línea. Existe un algoritmo eficiente para el caso de dos estudiantes, pero no se conoce ningún algoritmo eficiente para resolver el problema si cada habitación ha de ser compartida por tres estudiantes.

09:28

20 20

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. 09: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 09: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. 09: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

09:28

24 24

PROGRAMACIÓN II

La CLASE CO-NP, contiene todos los problemas cuya resolución es la disyuntiva "sí" o "no" y cuyas versiones complementarias pertenecen a NP. Es preciso ser cuidadoso al formular las preguntas al responder con un "sí" o un "no", pues el problema "no" o "sí" complementario al dado puede no pertenecer a la misma clase. Por ejemplo: El complementario del problema de los números compuestos: es determinar si un número es primo, pertenecería a la CLASE NP y esto no es así, porque ya se descubrieron algoritmos relativamente eficientes para probar el carácter primo de un número. A pesar de ello se desconoce si el problema de los números compuestos y su complementario pertenece a la CLASE P. Se necesitaron más de 100 años para demostrar que cierto número era compuesto. En 1640 Fermet conjeturó que el número 4.294.697.297, que es igual a 2^32 + 1 es un número primo, su error perduró hasta 1732 en que se descubrió que es igual a 6700417 x 641.

09:28

25 25

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

09: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.

09: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