Uno de los temas más debatidos y peor afrontados hoy día es el debate de la eficiencia: ¿qué es la eficiencia? Las definiciones más crueles suelen exigir que el proceso eficiente sea capaz de hacer las cosas bien y a la primera. Sin embargo algunos preferimos quedarnos con una definición más realista, como más útil. Porque no se trata de un concepto teórico, se trata de una idea muy práctica: preferimos decir que un sistema es eficiente cuando hace bien las cosas.
Lo primero que hay que hacer es distinguir la palabra eficiencia de la palabra corrección. Hacer las cosas al completo no es lo mismo que hacerlas bien (los matices entre lo correcto y la completitud estaría más detallado en la página anterior, hasta el punto de que sólo se trata de un matiz gramatical, no algo sustancioso).
De un lenguaje entendemos que su potencia de lenguaje (completitud) tiene que ver con los elementos que incorpora y el comportamiento que se les atribuye dentro del sistema, pero cuando hablamos de eficiencia nos referimos a la economía de los recursos necesarios para llevar a cabo tales gestiones. Por eso, de antemano, podríamos suponer que la eficiencia depende de la plataforma, de la notación usada, de en dónde se usa..., de la parte dura del sistema, su soporte físico: el hardware.
Sin ir más lejos, tenemos los últimos avances en inteligencia artificial, que tendremos que indagar más críticamente más adelante. Estos avances suelen centrarse en técnicas que han factorizado sus objetivos de manera que cada uno de ellos son abordados desde un punto de vista empírico para que funcionen con la idea conceptual que tenemos de ellos: lo llaman inteligencia artificial débil, yo lo llamaría más bien inteligencia chovinista. Pero ya habrá momentos para explicar todo esto...
Debido a que la última tecnología aprovecha todo el potencial de la máquina para esperar empíricamente un resultado antes de que aceptar un código, parecería que, efectivamente, la eficiencia debe depender de la plataforma: cuanto más potente sea una plataforma más eficiente puede hacer sus productos; que sólo funcionarán para ese tipo de plataformas.
Pues bien, lo dicho anteriormente es una filosofía, no un hecho. En informática existe una gran cantidad de tribus urbanas que defienden una manera de crear el código de manera que:
- La creación del código depende de una enorme plataforma y es un resultado empírico.
- El código resultante puede ser aprovechado eficientemente por máquinas ligeramente menos potentes.
- El código resultante no puede ser aprovechado eficientemente por máquinas mucho más potentes.
- La creación del código es un resultado de diseño plenamente analítico, con símbolos.
- El código resultante puede ser aprovechado eficientemente en cualquier máquina (a.k.a. escalable).
- Para máquinas menos potentes es fácil trasmigrar los resultados simbolistas para recrear atajos (a.k.a. heurísticas) en modelos estadísticos y funcionar con una filosofía no simbolista.
Pero centrémonos en el asunto en cuestión: un comportamiento dentro de un sistema decimos que es eficiente, ¿debido a su capacidad de acoplarse a su plataforma o hay en el comportamiento mismo una manera intrínseca y analizable que es capaz de dar a entender si en cualquier plataforma es o no eficiente?
Para entender más fácilmente la cuestión recurramos a la primera vez que surgió, según tengo entendido.
Hace años el eminente matemático John Nash fue consultado, o intercambiaron correspondencias, con la NSA. Se planteaba una duda importante: si cierto código que habían inventado podría ser vulnerable. Parece que hemos pegado un salto desde donde lo dejamos con las Máquinas de Turing a lo que estoy contando, ¿verdad? Pues no: en realidad es una continuación lógica.
El propio Alan Turing fue contratado por la inteligencia británica para descifrar el código nazi Enigma. La idea era diseñar una máquina mucho más potente de manera que sus engranajes y símbolos abarcaran todas las combinaciones que se planteaba la máquina de escribir nazi que encriptaba mensajes. Según parece debió funcionar. Máxime cuando observamos cómo Alan Turing seguía desarrollando su notación y sus máquinas virtuales, además de definir una idea de inteligencia o consciencia en la máquina.
Lo que le plantearon a Nash era si los rusos serían capaces de presupuestarse una máquina lo suficientemente compleja como para que los códigos fueran descifrables. Esto es, cuando se trata de adivinar un puzzle, podemos tener pistas sobre si cierta solución es la verdadera, pero eso no quiere decir que seamos capaces de ir escribiendo símbolo a símbolo la solución - pues para que sea comprobada es necesario tenerla al completo.
Así que la cuestión es: ¿es posible crear un sistema de encriptado que sea validable de manera que la máquina que lo desencripte (criptoanalice) suponga un coste intratable? Para que el problema pueda ser resuelto antes debe plantearse dentro de una notación general, así que es fácil imaginar cuál va a ser dicha notación,
¿Existe la configuración de una Máquina de Turing que valide fácilmente si el par (entrada, salida) cumple que la salida se encripta con la forma que tiene la entrada de manera que sea posible encontrar otra configuración de una Máquina de Turing que criptoanalice fácilmente la salida a partir de la entrada?
Como se puede comprobar, nuestro principal problema es que el problema está planteado de manera muy ambigua aún ¿Qué significa operar fácilmente? Desde un punto de vista del interés por la construcción de una máquina física, estaríamos hablando de la capacidad que podría tener un gobierno para juntar los recursos necesarios que permitan generar dicha máquina.
Para poder resolver ésto, podemos plantearnos una idea muy simple: si el tiempo que necesite una máquina en resolver su operación no supera una expresión polinomial (complejidad polinomial) con respecto al tamaño de la entrada, entonces el problema nos parecerá complejo cuanto mayor sea el exponente del polinomio, pero sería presupuestable. Para exponente 1, la complejidad sería lineal; para exponente 2, la complejidad sería cuadrática... Cuando no sea menor que un polinomio diremos que es demasiado complejo, o intratable.
Es cuestión de imaginarse: una máquina que tarda 5 segundos en dar una respuesta por cada símbolo que tenga la entrada, si son 20 símbolos para que la máquina tarde 5 segundos en responder sólo necesitaría ser 20 veces más cara, pero si la complejidad fuera cuadrática sería 400 veces más cara. La cosa es que no pueda asociarse ningún polinomio, para que el coste en ningún momento fuera asumible. Por ejemplo: cuántas veces deberíamos de jugar a la lotería comprando un único boleto para que ganemos el premio gordo por primera vez; el tiempo de espera es inasumible aunque pase a celebrarse un sorteo todos los días, o incluso a todas horas.
Por tanto, nos interesa plantearnos cuándo una configuración podemos asegurar que se resuelve dentro de una cota polinomial con respecto al tamaño de la entrada. En cuanto a cómo representar la operación de criptoanálisis con respecto a la criptografía, el propio Alan Turing adelantó un tipo de máquina que recordaba mucho la idea que tenemos de actuar conscientemente: ¿qué pasaría si a algunos de los símbolos y técnicas para trabajar la notación se le incorporara caracteres comodín para que un agente consciente se encargara de ponerles el valor más adecuado? A este tipo de máquinas las llamó Máquinas de Turing No Determinísticas, pues el siguiente paso a llevar a cabo está limitado por un número finito de posibilidades, pero habría que testarlas una a una antes de concluir cuál adoptar.
Tras un estudio suficientemente meticuloso uno puede comprender que el verdadero problema expuesto al principio de manera que sea más fácil de entender dentro de una notación rigurosa sería:
Si existe alguna clase de problemas cuya configuración en las Máquinas de Turing No Determinísticas acotadas polinomialmente no es posible encontrarle una configuración en una Máquina de Turing (determinística) sin que deje de estar acotado polinomialmente.
Por eso mismo, si un problema es una pregunta que desemboca en un estado final "SÍ" o en un estado final "NO" exclusivamente, entonces ya estamos preparados para definir los problemas que estén acotados polinomialmente dentro de una Máquina de Turing No Determinística como NP. Mientras que los problemas que estén acotados polinomialmente dentro de una Máquina de Turing [determinística] serán considerados dentro de la clase P. Por lo que la pregunta final es: ¿NP = P?
No hay comentarios:
Publicar un comentario