Para medir la complejidad de los c�lculo es la cantidad de espacio de almacenamiento requerido. Esto se basa en el supuesto de que, conforme aumenta la complejidad de un c�lculo, el espacio de almacenamiento se necesita para su ejecuci�n. La cantidad de este es de almacenamiento que requiere un c�lculo se conoce como complejidad parcial.

La complejidad espacial de un c�lculo de una m�quina de Turing se define como el n�mero de celdas de la cinta que dicho c�lculo requiere. As�, si la complejidad espacial de una m�quina de Turing fuera 9, la m�quina utilizar�a las primeras nueve celdas de la cinta durante sus c�lculos pero no requer�a que estuviera presente el resto de la cinta.

Para decir si un algoritmo es complejo hay que basarse en la cuesti�n de si los c�lculos son complejos o no.
Cada m�quina de Turing no es m�s que la implantaci�n de un algoritmo representado en la forma del diagrama de transiciones de la m�quina.

La t�cnica que utiliza nuestra m�quina de Turing es comparar repetidamente los elementos correspondientes de las cadenas hasta haber considerado todos los pares o detectar una discrepancia. Esto se hace leyendo el primer s�mbolo de la primera cadena y luego moviendo la cabeza hasta el primer s�mbolo de la segunda, para confirmar si son iguales. Si lo son, la m�quina regresa a la primera cadena para observar el segundo s�mbolo antes de pasar a la segunda cadena y verificar que su segundo elemento sea igual. As� es el proceso de comparaci�n da como resultado que la cabeza de la cinta alterne entre las dos cadenas conforme se comparan sus elementos.

Cuando nos enfrentamos a un problema concreto, habr� una serie de algoritmos aplicables. Se suele decir que el orden de complejidad de un problema es el del mejor algoritmo que se conozca para resolverlo. As� se clasifican los problemas, y los estudios sobre algoritmos se aplican a la realidad.

Estos estudios han llevado a la constataci�n de que existen problemas muy dif�ciles, problemas que desafian la utilizaci�n de los ordenadores para resolverlos. En lo que sigue esbozaremos las clases de problemas que hoy por hoy se escapan a un tratamiento inform�tico.
Clase P.- Los algoritmos de complejidad polin�mica se dice que son tratables en el sentido de que suelen ser abordables en la pr�ctica. Los problemas para los que se conocen algoritmos con esta complejidad se dice que forman la clase P.

Clase NP.- Algunos de estos problemas intratables pueden caracterizarse por el curioso hecho de que puede aplicarse un algoritmo polin�mico para comprobar si una posible soluci�n es v�lida o no.

Clase NP-completos.- Son problemas NP, y son los peores problemas posibles de clase NP. Estos problemas se caracterizan por ser todos "iguales" en el sentido de que si se descubriera una soluci�n P para alguno de ellos, esta soluci�n ser�a f�cilmente aplicable a todos ellos. Actualmente hay un premio de prestigio equivalente al Nobel reservado para el que descubra semejante soluci�n ... �y se duda seriamente de que alguien lo consiga!

Algunos de estos problemas intratables pueden caracterizarse por el curioso hecho de que puede aplicarse un algoritmo polin�mico para comprobar si una posible soluci�n es v�lida o no. Esta caracter�stica lleva a un m�todo de resoluci�n no determinista consistente en aplicar heur�sticos para obtener soluciones hipot�ticas que se van desestimando (o aceptando) a ritmo polin�mico.
Los problemas de esta clase se denominan NP (la N de no-deterministas y la P de polin�micos).

Existen problemas irresolubles que se pueden plantear en el lenguaje de la teor�a de la computabilidad.
El "problema de la parada" para m�quinas de Turing es pues irresoluble mediante m�quinas de Turing.
El teorema de Rice que indica que no hay manera alguna de reconocer procedimentalmente clases "interesantes" de funciones.
Otro problema cl�sico irresoluble, es el de la "correspondencia de Post".
A partir de �ste, muchos problemas de decisi�n, planteados para gram�ticas libres de contexto, vale decir, para gram�ticas en los primeros niveles de la Jerarqu�a de Chomsky, son tambi�n irresolubles. Finalmente, el equivalente a la noci�n de irresolubilidad en la L�gica Matem�tica. En �sta, una demostraci�n consiste, al igual que una computaci�n, de una secuencia de transformaciones para derivar teoremas. Un enunciado indemostrable es entonces uno inaccesible mediante las reglas de deducci�n de la teor�a.

La informaci�n la obtuve de:

WWW.ALTAVISTA.COM.MX
WWW.YAHOO.COM.MX
WWW.GOOGLE.COM

Y si tienen Quejas, Sugerencias o Felicitaciones: Mandame un mensaje de correo