PROBLEMAS ALGORÍTMICOS

José María Gómez Aroca

Álgebra IV - Facultad de Matemáticas - Universidad de Murcia

Dedico este trabajo al que fue mi profesor de esta asignatura
Dr. D. José Luis Gómez Pardo

PROBLEMAS DECIDIBLES E INDECIDIBLES

Para cada n número entero.

        (a) ¿ Existe p>n tal que p es primo?
        (b) ¿ Existe p>n tal que p y p+2 son ambos primos?

Entre estos dos problemas hay una diferencia sustancial. Para resolver el primero podemos utilizar un algoritmo que busque un número primo mayor que n. Como hay infinitos primos sabemos que el algoritmo encontrará el primo buscado y se detendrá respondiendo afirmativamente a la pregunta. El segundo problema es muy distinto. No sabemos si la cantidad de primos gemelos (pares de la forma p,p+2 ambos primos) es finita o infinita. Si vamos probando con valores de n y siempre encontramos un par de primos gemelos mayores que n, no podemos asegurar que esto se verifique para todos los posibles valores de n. No podemos responder a la pregunta en este caso. Si ante un valor n observamos que el algoritmo que utilizamos no se detiene, tampoco se puede responder a la pregunta. Tal vez el algoritmo no se detenga nunca o tal vez se detenga en el próximo segundo. Este hecho nos hace pensar en dos clases:

        1.- La clase de los problemas decidibles o computables, que admiten un algoritmo que los resuelve; es decir, para todo posible valor de las variables de entrada, el algoritmo se detiene eventualmente dando como salida la solución 
correcta al problema.

    2.- La clase de los problemas indecidibles o no computables, que no admiten un algoritmo que los resuelva. Pasemos a conocer algo más de estas dos clases.

TIEMPO RAZONABLE Y NO RAZONABLE
Supongamos que estamos ante un problema decidible y conocemos el algoritmo que lo resuelve. ¿De qué nos sirve este algoritmo si tarda en darnos la solución cien años?.

Antes de utilizar un algoritmo debemos estimar el tiempo que tardará en solucionar el problema y ver si este tiempo es razonable. Pero, ¿cuándo un tiempo es razonable?. Si observamos la tabla anterior, parece que lo más natural es considerar como razonables los tiempos que están acotados por un polinomio (dependiente del tamaño de las variables de entrada). Usando la notación O mayúscula, serán los tiempos de la forma O(p) siendo p un polinomio.


LAS CLASES P Y NP
Diremos que un algoritmo A tiene complejidad de tiempo polinómico si existe un polinomio p(x), tal que el tiempo máximo requerido por A para dar una solución sobre una entrada de tamaño n es T_A(n)=O(p(n)). La clase P es la clase de los problemas que se pueden resolver con un algoritmo que tiene complejidad de tiempo polinómico. A este tipo de problemas se les suele llamar también tratables y a los computables que no son tratables, intratables. Entre los problemas intratables existe una clase, que tiene una característica común, pueden ser resueltos en tiempo polinómico por un algoritmo no determinista. Esta clase se llama NP (no deterministic polinomial). Si A es un problema de la clase P, entonces A puede resolverse en tiempo polinómico por un algoritmo determinista y por lo tanto será resuelto en tiempo polinómico por un algoritmo no determinista; es decir, P está contenido en NP. Si P no es igual a NP, entonces un problema de NP-P no puede resolverse en tiempo polinómico, pero una vez resuelto puede ser probado en tiempo polinómico. Basta construir un algoritmo determinista que siga el mismo camino que seguiría un algoritmo no determinista (conocemos este camino pues hemos resuelto previamente el problema), y la complejidad de tiempo del algoritmo determinista sería, obviamente, polinómico. 

EJEMPLOS
        (a) El cálculo del máximo común divisor está en P. Por el algoritmo de Euclides, si a>b, entonces T(mcd(a,b))=O(a³).
        (b) Probar que un número es compuesto está en NP. Ningún algoritmo conocido para este problema tiene complejidad de tiempo polinómico. Conocido un factor, probar que el número es compuesto se realiza en tiempo polinómico. A esta información adicional que nos permite probar un problema NP en tiempo polinómico, se le llama un certificado.
        (c) Probar que un número es primo está en NP. (V. Pratt-1975). El dual de un problema de la clase P está en P. ¿ Ocurre lo mismo en la clase NP ?
        (d) Probar que un grafo es hamiltoniano está en NP. El número de posibilidades a comprobar es exponencial, pero conocido el camino adecuado se prueba en tiempo polinómico. Probar que un grafo no es hamiltoniano no parece estar en NP, pues no se ve la forma de dar un certificado.
        (e) Un ejemplo interesante es el de los grafos eulerianos. Este problema no está en la clase P pues hay que comprobar del orden de N²! posibilidades. La intuición nos engaña esta vez. En 1736, Euler dio una condición equivalente al hecho de que un grafo sea euleriano, y lo que es más, esta condición puede ser probada en tiempo polinómico. (El numero de líneas que parten de cada vértice, con la posible excepción de dos, es par). ¿ Podría ocurrir esto con los demás problemas de la clase NP ?. O dicho con otras palabras, ¿ P=NP ? 

PROBLEMAS NP-COMPLETOS
    La respuesta a las preguntas anteriores no es conocida todavía. Una primera aproximación fue dada por Cook en 1971. Un problema P se dice que es NP-difícil, si todo problema de NP es polinómicamente reducible a él. P se dice que es NP-completo, si P es NP-difícil y además, está en NP. El teorema de Cook puede enunciarse de la siguiente forma: "Existe un problema NP-completo". Con este resultado, si probamos que un problema NP-completo está en P, entonces P=NP ya que todo problema de NP se puede reducir en tiempo polinómico al problema NP-completo y este se resuelve en tiempo polinómico. Para ver que un problema P es NP-completo basta ver que un problema  NP-completo conocido R se reduce polinómicamente a él. De esta forma, todo problema de NP se reduce a R y R se reduce a P, por lo tanto, todo problema de NP se reduce polinomicamente a P; es decir, P es NP-completo. Este tipo de prueba no sirve para encontrar un primer problema NP-completo, evidentemente.

EJEMPLOS
        (a) El problema de la satisfactibilidad es NP-completo.
        (b) El problema de la mochila es NP-completo.
                Computation and Automata. Arto Salomaa. (Pags. 168 y 173) 

PROBLEMAS INDECIDIBLES
    La cuestión a la que nos enfrentamos ahora es la siguiente: ante un determinado problema como saber si el problema es decidible o indecidible. La respuesta parece obvia, bastará con ver si podemos encontrar un algoritmo que 
resuelva el problema. En la práctica esto no es tan sencillo por diferentes razones:

        (1) Si no encontramos un algoritmo, no quiere decir que éste no exista.
        (2) Si encontramos un algoritmo, ¿ se detendrá para toda posible entrada y nos dará la respuesta correcta ?.
            ¿ Cómo averiguar si un problema es indecidible ?

Ej.: Problema de la sucesión: Sea a₀ número entero positivo. Sea a_n+1=a_n/2 si a_n es par y a_n+1=3a_n+1 si a_n es impar. 
¿ Existe algún término de la sucesión que sea igual a uno ?.

EL PROBLEMA DE LA DETENCION
Sea L un lenguaje de programación, R un programa escrito en el lenguaje L y X una posible entrada de R. El problema de la detención pregunta si R se detendrá cuando lo ejecutamos dándole a X como entrada. Supongamos que existe un programa Q que acepta como entrada pares (R,X). Si R se detiene cuando lo ejecutamos con la entrada X, entonces Q nos responde "si" cuando lo ejecutamos con la entrada (R,X). Si R no se detiene con X, entonces Q nos responde "no". Sea S un programa que espera a que Q termine. Si Q responde "si", S entra en un bucle infinito (no se detiene), y si Q responde "no", S se detiene. Si ejecutamos Q dando (S,S) como entrada y Q responde "si", quiere decir que S se detiene pero entonces S no se detiene, y si Q responde "no" es porque S no se detiene pero entonces S se detiene. Esto es contradictorio y, por lo tanto el problema de la detención es indecidible.


PROBAR LA INDECIDIBILIDAD
Dado un problema P, si el problema de la detención H es reducible (sea polinómicamente o no) a P, entonces P es indecidible. Si P fuese decidible, tambien lo sería H, pero sabemos que no lo es. Analogamente, si P es decidible y Q es reducible a P, entonces Q es decidible. No todos los problemas indecidibles son iguales en cuanto al grado de 
indecidibilidad. Por ejemplo, en el problema de la sucesión, para un valor a₀ determinado ejecutamos un programa que calcula los términos a_i  ( i=1,2,....). Si la sucesión alcanza el valor uno y se detiene el problema es, en este caso, 
decidible. Si la sucesión no alcanza el valor uno, la sucesión no se detendrá nunca, pero no podemos saber que no se detendrá. Este es un problema de los llamados parcialmente indecidibles o indecidibles. Otro tipo son los altamente 
indecidibles, en lo que no está asegurada la respuesta en ninguno de los casos.


LOS CUATRO NIVELES FUNDAMENTALES

    Cuando comenzamos a leer este trabajo, todos los problemas estaban englobados en una misma clase. Después distinguimos problemas decidibles de indecidibles, y más tarde vimos que los primeros podían ser tratables o intratables, mientras que los últimos podían ser indecidibles o altamente indecidibles.

    Desde el punto de vista de la computación sólo los problemas tratables admiten algoritmos eficaces. Tener en cuenta que indecidible quiere decir aquí algorítmicamente indecidible y podrían existir métodos no algorítmicos para resolver el problema en cuestión. Esto nos lleva al concepto usual de indecidible matemático, para el cual no existe ningún medio de probar su verdad o falsedad.


UN ÚLTIMO PROBLEMA

        Llamaremos a este problema, el problema de la serpiente. Sea T un conjunto formado por un número finito de cuadrados. Cada cuadrado está dividido por sus diagonales en cuatro partes y cada una de ellas dibujada con un color, que puede repetirse en un mismo cuadrado o de un cuadrado a otro. Los cuadrados se consideran orientados de una determinada forma (no está permitido girarlos). Consideremos dos posiciones V y W dentro de un recinto R del espacio afín R². En estas dos posiciones colocamos dos elementos de T (dos cuadrados). Se trata de ir colocando cuadrados uno a continuación del otro sin salirse del recinto R hasta unir V con W, con la siguiente condición: un cuadrado puede unirse a otro si, y sólo si, los lados adyacentes tienen el mismo color. Dado un conjunto T determinado y dos cuadrados en las posiciones elegidas, ¿es posible unir V con W de la forma que hemos señalado?

        La decidibilidad del problema de la serpiente depende de R. Si R está acotado, el problema es decidible pues sólo hay que comprobar un número finito de posibilidades.

        Si R es un semiplano, el problema es parcialmente indecidible. Si existe una solución, un algoritmo la encontrará con solo ir probando de forma exhaustiva todos los caminos posibles. Si no la hay, puede ocurrir que el hipotético algoritmo tenga que comprobar infinitas posibilidades, con lo cual nunca se detendría y nunca conoceríamos la respuesta.

        Si R es todo el plano R2, el problema es decidible. ¿Por qué? Aparentemente parece ser un caso similar al del semiplano, y sin embargo debe haber algún modo de encontrar la respuesta sin comprobar las infinitas posibilidades.

Espero vuestras opiniones y/o soluciones en mi correo:  jgomez53(arroba)mimosa.pntic.mec(punto)es-nocorreobasura