Ciencia y Tecnología

En la página anterior de Ciencia y Eficiencia se presentó una pregunta crucial para dejarla en el aire. Quizá me vea en la obligación de completar esa página con más información para aprovechar la coyuntura de rellenarla con datos que sean relevantes. Ahora es en esta página cuando voy a empezar a ser heterodoxo. En este punto empiezo a explicar en qué consisten mis matices.




Como se ha mencionado anteriormente, tenemos dos maneras de estudiar la tecnología: una es aprovechando al máximo los recursos que nos ofrece la plataforma para intentar hacer que ésta se acople al entorno hostil que le hace uso y la otra es diseñando productos independientemente de cada plataforma para así ir desechando los soportes físicos que sean lentos.

Cuando un jugador de ajedrez experto se enfrenta contra un novato, por muy buena máquina que tenga el novato por cabeza, el experto conoce aperturas y sabe posicionarse con estrategias que le favorecen. Si el novato sale con una variación importante, a un verdadero experto no se le caerán los anillos.

Y esta es la situación actual: de todas las aportaciones que se han hecho dentro de la teoría de la complejidad existe un teorema realmente increible que resolvería de un chasquido de dedos el 50% de las preguntas más inmediatas que podríamos plantearnos.

Los problemas que son susceptibles de ser resueltos en Máquinas de Turing son los mismos que se podrían resolver en landa-cálculo, como así se ha estado estableciendo paralelismos con lenguajes de programación bajo el paradigma imperativo (la configuración de la máquina es una secuencia de instrucciones que incorpora bucles y llamadas recursivas a funciones). Esto ha provocado que los problemas, descritos en un lenguaje natural-técnico (inglés técnico, castellano técnico), pudieron ser etiquetados y clasificados más fácilmente; hasta el punto de crear una topología de la transformación de un problema en otro.

Es aquí donde entra en juego la idea de: ¿se podría reducir los problemas dentro de la clase NP a un problema lo suficientemente duro como para que resolviendo éste se resuelva el resto? Bueno, pues según Stephen Cook, sí. La idea de los problemas que se encuentran en la clase NP-completo consiste en aquellos problemas que tienen una transformación equivalente a tener que resolver un problema NP-completo específico que, según el caso, fue llamado SAT. Es decir, según el teorema de Cook, quienquiera que resuelva en tiempo polinomial dentro de una Maquina de Turing un problema dentro de la clase NP-completo habrá resuelto SAT que, a su misma vez, es capaz de resolver cualquier problema NP. Por lo que habrá demostrado que NP = P mediante un contraejemplo.

Tengo buenas noticias. Efectivamente desde hace años ya encontré una estructura capaz de resolver SAT en tiempo polinomial, escrito en Python mediante recursivas primitivas (bucles for). Pero, ¿qué es SAT? El problema SAT consiste sorprendentemente en determinar si una fórmula booleana de productos de sumas de literales tiene una asignación posible para que devuelva 1. Sabiendo que un literal es una variable booleana que puede o no ser negada, al final lo que observamos es una inconsistencia entre lo que he descrito en la primera página (Ciencia y Razón) y lo que afirma sir Stephen Cook, ¿alguno de ustedes es capaz de comprobar qué es?

Recapitulemos antes de nada:

1. Stephen Cook demostró matemáticamente que todos los problemas que puedan ser descritos dentro de la clase NP pueden ser descritos mediante una cota polinomial con respecto al tamaño de la entrada mediante la igualdad de 1 a un producto de sumas de literales booleanos. Más simple: todos los NP se pueden describir fácilmente mediante SAT.
2.  La ciencia no parece querer conformarse con la completitud que ofrece las proposiciones lógicas si no incorpora predicados de alguna manera.
3. Para ofrecer más potencia usamos Máquinas de Turing. Pero hay problemas que somos capaces de plantearnos aunque no estemos seguros de cómo llevar a cabo la solución.
4. Para ofrecer más potencia a las anteriores se crea las Máquinas de Turing No Determinísticas.
5. Decidimos acotar las anteriores a partir del tamaño de la entrada.
6. Para controlar la gestión de las máquinas más potentes nos conformamos con una lógica de juguete...

Bueno, voy a ir poniendo un poco de orden. Para empezar, las matemáticas tienen dos filosofías. Una de ellas es constructivista y la otra es no-constructivista. El constructivismo consiste en decir que no aceptas una demostración salvo que se constituya en la misma un conjunto de reglas de manera que, recursivamente, encontremos desde lo más básico el resultado perfectamente justificado y constituido. Como si fuera un producto de ingeniería.

La otra filosofía algunos la vuelven a subdividir entre axiomáticos y formalistas, para el caso quizá no sea demasiado importante la diferencia entre ambos: esta otra filosofía se conforma con todas las afirmaciones que no puedan sucumbir a una contradicción. Esto es, si se puede crear una teoría consistente entonces aceptamos tal teoría.

Ambas filosofías son exactas, en la medida de que no se puede decir que la menos rigurosa (el formalismo) exponga modelos erróneos - porque en ausencia de contradicción todo es igual de válido. Sin embargo, no es lo mismo aseverar una prolongación de unos preceptos aceptados que encontrar unas afirmaciones independientes (algo que, como corolario de los dicho anteriormente, se va a dar mucho).

Así que, cuando observamos el teorema de Cook, muchos dirán que la demostración es constructivista (porque Cook nos describe cómo construir la Máquina de Turing) sin embargo aquí vuelve mi punto de vista heterodoxo a criticar: Cook nos ofrece una demostración formalista. Esto es porque para construir la máquina antes parte del supuesto de que ya se ha resuelto el problema, por lo que la máquina construida no está pensada para resolver problemas. Éste es el detalle más importante y lo más esencial del asunto: las conclusiones se constituyen a partir de una información que no tenemos.

Cuando examinamos mis conclusiones, podemos comprobar que, efectivamente, hay cosas que no cuadran: ¿por tener resuelto SAT voy a poder crearme un lenguaje de la lógica proposicional atómica de manera que pueda abordar cualquier problema NP? ¿Nos hemos vuelto locos? Por supuesto, cuando resolví SAT eso fue lo primero que busqué, porque el teorema de Cook me lo aseguraba; sin embargo, ese mecanismo no existe. Efectivamente: el teorema de Cook no sirve para resolver.

Si cambiamos la filosofía, podemos observar una peculiar resolución: ¿qué ocurre cuando no puedo jugar con la configuración de la Máquina de Turing? ¿qué ocurre cuando esa información no la tengo disponible y debo manejarme de manera estática? Pues de ahí nace mi otra demostración. Este otro ensayo empieza a meter mucha más traya:

Desde un punto de vista constructivista ASEGURO:

1. NP es distinto de P.
2. SAT dentro de P.
3. TQBF = SAT. 
4. Existe un algoritmo sencillo que unifica los existenciales para hacer que cualquier teorema sea como resolver cualquier tautología que, a su misma vez, se reduce a resolver SAT.

Desde un punto de vista formalista ASEGURO:

1. #SAT dentro de FP. 
2. TQBF es de la clase PSPACE-completo.
3. Un PSPACE-completo resuelve cualquier PSPACE.

 Sin embargo, SABEMOS:

1. FP  es la clase de las funciones que se resuelven en tiempo polinomial.
2. Los miembros de la clase FP se pueden degradar a la clase P.
3. #X es la función que resuelve el número de casos que satisface el NP llamado X.
4. #X siempre es más potente que X.
5. TQBF es el problema de satisfacer cualquier función booleana con cuantificadores.
6. La clase de los NP está comprendida en el interior de los PSPACE.

En el mismo ensayo planteo que el formalismo no puede resolver sus directrices desde un punto de vista de la filosofía simbolista, sino desde un punto de vista no-simbolista. Esto es, aprovechando que se tiene conocimiento de cómo es la plataforma. De esta manera, todos los resultados son susceptibles de ser aprovechados dentro de su filosofía correcta.


No sé si he conseguido transmitir toda la bomba que es..., pero por supuesto, esta no es mi mejor tecnología. Aún están las cosas que no puedo o no he sabido demostrar, así como las que quedan por investigar y que me parecen mucho más fascinantes y útiles.