Breve introducción a la teoria de la complejidad y metodos alternativos de computación ( I ) Complejidad computacional: Tenemos dos algoritmos que resuelven un mismo problema, Contabilizando el numero de operaciones elementales que realiza:
Por ejemplo: func buscar(a:vector; c:elemento) dev(r:entero) var j:entero alg j:=1 // 1 1 OE mientras a[j]c yj<n // 2 4 OE j:=j+1 // 3 2 OE fmientras // 4 si a[j]=c: // 5 2 OE r:=j // 6 1 OE | otros: r:=0 // 7 1 OE fsi // 8 fin Se pueden analizar 3 complejidades diferentes: El caso mejor: que el algoritmo no entre en el “mientras” nunca ni en el “si” tampoco: ![]() El caso peor: que entre n-1 veces en el bucle mientras: ![]() El caso medio: que se obtiene analizando la probabilidad que existe de que entre 1 vez en el bucle, 2 veces, 3 veces... y obteniendo el numero medio de veces que entrará: ![]() ![]() A partir de los analisis temporales podemos definir el concepto de orden de complejidad, Aunque dos algoritmos para un mismo tamaño (n) tarden muy poco, si analizamos su orden podremos observar como crece a medida que crece la entrada: ![]() Si nos fijamos, cuando el orden es un polinomio el problema se puede manejar más o menos, pero cuando
tiene un valor exponencial el tiempo se dispara al crecer la entrada. Problemas intratables: Cuando no se conoce un metodo para resolver un problema en un tiempo razonable (polinomial), se le da el
adjetivo de problema intrable. P versus NP
![]()
![]() Por un lado comprobamos que los problemas P estan contenidos en los NP, puesto que seria usar una sola rama. La duda esta en... ¿NP esta contenida en P? ![]() La verdad, nadie ha demostrado por ahora si P = NP a pesar de dedicarse varios cientos de millones de
dolares al año en esta conjetura. Si eso fuese verdad, y P = NP, está demostrado que cualquier problema NP se podria trasformar
en uno P por un proceso mecanico. El caso es que los problemas NP estan ahí, sus soluciones son necesarias, y por ahora no hay
manera de atacarlos, al menos con computación convencional. Se pueden obtener aproximaciones pero
para algunas aplicaciones no basta con una aproximación. Computacion natural: Está demostrado que por mucho que se miniaturicen los componentes electronicos, existe un punto en el que no se pueden apretar más, puesto que se solaparian. Se puede pues comprobar que la tecnologia basada en la manipulacion electronica del silicio tiene un limite en muy poco tiempo se alcanzará. Es como si existiese una linea tal que así: ![]() Se podria pensar que con muchos ordenadors convencionales en paralelo se llegaria más lejos, lo cual es falso puesto que esa linea aumenta exponencialmente. Con milones de ordenadoes solo podriamos alejar el limite un poco. Es necesario encontrar otros modelos en los que se puedan representar modelos que sean más pequeños y más rapidos, ahí se encuentran los modelos basados en computacion natural. ![]() Basandose en ciertos comportamientos de la naturaleza se han desarrollado teorias, y modelos de computación en los que si existen soluciones a augas instancias de problemas NP. ![]() Por ejemplo, puesto que tenemos que atacar un problema para el cual se necesitaria un tiempo exponencial del cual
no disponemos, codificando el problema en en moleculas de ADN se puede obtener un “espacio exponencial”
mediante el cual se suple en parte la falta de tiempo. ![]() Por supuesto todo esto se esta desarrollando teniendo en cuenta que es muy probable que P no sea igual a NP,
porque si P=NP todo es inutil, podria resolverse practicamente todo lo resoluble. Continuará... |