EZINE HISPABYTE

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,
¿Cómo sabemos cual de los dos es mejor?
Podriamos pensar: Los ejecuto y cronometro, el que tarde menos es el mejor.
Sería una forma, pero la manera más acertada de medirlos es sobre el papel.

Contabilizando el numero de operaciones elementales que realiza:

  • Llamadas a una funcion
  • Operaciones aritmeticas
  • Acceso a un array
  • Operaciones logicas.
A partir de ahí podremos dar una expresión que nos mostrara el tiempo de ejecución a partir del tamaño que le asignemos al problema.

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:

BIALATDLCYMADC_html_16015532.png

El caso peor: que entre n-1 veces en el bucle mientras:

BIALATDLCYMADC_html_613e717f.png

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

BIALATDLCYMADC_html_m69c1c828.png
BIALATDLCYMADC_html_2cbc1af5.png

A partir de los analisis temporales podemos definir el concepto de orden de complejidad,
En el caso mejor pertenece al orden constante O(1) , puesto que no depende del tamaño de la entrada (n).
En los otros dos casos el algoritmo pertenece a un oden linea O(n).

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:

BIALATDLCYMADC_html_m1c89a348.png

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.
Ahí entra el concepto de problema intratable.

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.
La seguridad de las comunicaciones se basa en la creencia de que no existe un algoritmo polinomial para todos los problemas.

P versus NP

  • Podemos agrupar e un conjunto llamado P a todos los problemas resolubles por una maquina determinista en un tiempo polinomial (es decir, un ordenador).
BIALATDLCYMADC_html_m5f3c3a3f.gif
  • Tambien podemos agrupar en un conjunto NP a todos los problemas resulubles por una maquina no determinista (hipotetica) en tiempo polinomial (resolubles pos una maquina determinista en tiempo exponencial).
BIALATDLCYMADC_html_3f32b26c.gif

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?

BIALATDLCYMADC_html_706878f8.png

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.
Es el problema matematico abierto mas importante de los ultimos tiempos.

Si eso fuese verdad, y P = NP, está demostrado que cualquier problema NP se podria trasformar en uno P por un proceso mecanico.
Se desencadenaria un pequeño apocalipsis, la seguridad basada en clave publica se desmoronaria, puesto que en poco tiempo se podria descubrir cualquier clave que por fuerza bruta tardaria varias veces la edad del universo. Se podrian demostrar conjeturas matematicas en cuestion de segundos... si alguien ha demostrado esto puede que algun gobierno no deje que salga a la luz jamás...

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.
Ahi es donde comienza toda la teoria de Computacion natural:

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

BIALATDLCYMADC_html_m79b6d567.gif

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.

BIALATDLCYMADC_html_m3315477e.gif

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.

BIALATDLCYMADC_html_m44fa995.png

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.
Mediante membranas celulares se pueden implementar maquinas no deterministas... toda una nueva era de maquinas no basadas en la manipulacion electronica del carbono para atacar problemas muy importantes para el ser humano que no tienen solución ( a no ser que P = NP ).

BIALATDLCYMADC_html_m59b282eb.gif

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