Tengo un problema : soy daltónico. Bueno, no realmente, es solo que distingo mal algunos colores cuando son muy parecidos. Usted me dirá que le pasa a todo el mundo. Digamos entonces que yo distingo mal los colores que tal vez usted sí distinguiría.

Un problema de colores de calcetines

Esto es lo que pasó el otro día. Muy temprano (no tan temprano, pero esto es otra historia), estaba poniéndome los calcetines, medio dormido, cuando mi hija de 4 años exclamó : ’’¡Cómo ! ¡No te has puesto calcetines del mismo color !’’ (eso le hizo reír mucho, además, porque le encanta jugar a eso, pero esto también es otra historia). Me miré los pies y ahí todo se puso feo : no, mis calcetines eran del mismo color.

Mi hija se larga a reír, llama a su hermano mayor, que también se ríe. Algunos minutos después, mis tres hijos están ahí, alrededor mío, muertos de la risa delante de mis calcetines, diciendo que uno era gris y el otro azul, aunque para mí ambos eran grises.

Yo creí que estaban haciéndome una broma. Además, ¡se reían tanto ! Protesté vanamente, pese a que en un momento les contesté : ’’¡OK, demuéstrenme que ambos son de colores diferentes !’’

— Bueno, dijo la otra hija, son de colores diferentes, eso es todo.
— Puede ser, pero no te creo. Pruébamelo.
— ¿Puedo ir a buscar a la mamá ?
— No, tampoco le creeré a ella (bueno, sí, le habría creído, pero esa es otra historia...).
— No es posible, si tú no quieres creernos.

Ahí fue cuando empecé a divertirme...

— Eh sí, es posible, y voy a mostrarles cómo.

Una solución al problema

Me saqué los calcetines, tomé uno en una mano y el otro en la otra, y les pregunté cuál era azul y cuál era gris. Después me di la vuelta, cambié los calcetines de mano varias veces sin mostrarles lo que hacía, pero recordando bien (aunque no era fácil...) dónde debería estar el calcetín supuestamente azul, y dónde está el gris.
Después les pregunté :

— Y ahora ¿cuál es el azul ?

Y ellos, al unísono, dijeron :

— ¡Es el de la derecha !

Me embaucaron : ¡tenían razón ! Por supuesto, yo no sabía si ese era azul o gris, ya que no veía la diferencia con el de la mano izquierda, pero lo que sí sabía es que había cambiado los calcetines de mano, y que al principio me habían dicho que el azul estaba en la izquierda.

Me dije que tal vez habían tenido suerte (aunque si estaban los tres de acuerdo debía haber un fondo de verdad), y recomencé el experimento dos veces, tres veces, diez veces... Ellos nunca se equivocaron. Terminé por creerles : si ambos calcetines hubieran sido idénticos, como yo creía, ¿cómo podrían haber adivinado si yo había cambiado los calcetines o no ?

Entonces ordené mis dos calcetines en el armario y tomé otro par... con rayas, el único par que tengo de ese estilo.

Conclusión

¿Vale la pena decir que esta historia es inventada, como lo son todas las buenas historias ? Lo que la provocó fue mi lectura del libro de Sanjeev Arora y Boaz Barak, Computational Complexity : A Modern Approach.

El capítulo 8 del libro de Arora y Barak está dedicado a las pruebas interactivas.
Introducidas en 1985 por Goldwasser, Micali y Rackoff por una parte, y Babai por otra, una prueba interactiva permite certificar (rápidamente) la respuesta a un problema, con la condición de someterla a una serie de preguntas elegidas aleatoriamente por un tercero. La historia anterior es una variante del ejemplo 8.5 de ese libro.

A la pasada, un comentario divertido : en una versión provisional de ese libro que circula en la web, se encuentra un ejemplo un tanto distinto : los autores explican ahí cómo convencer a un interlocutor para diferenciar entre dos bebidas gaseosas con cafeína...

Mi historia se detiene ahí, pero siento que usted está impaciente por saber más. Si es ese el caso, quédese en el café y pida otro, ya que va a ponerse un poco más complicado.

La teoría de la complejidad

La teoría de la complejidad se propone estudiar cuáles problemas son resolubles de manera mecánica, algorítmica, en especial con ayuda de un computador, técnicamente una máquina de Turing.
Pone el acento sobre todo en las restricciones requeridas para la solución de tal problema : ¿cuánto tiempo toma en función de los datos ? ; ¿cuánto espacio de memoria necesita ? En función de la manera de evaluar esta complejidad y de los medios dados a una máquina, los especialistas han identificado entonces cerca de 500 clases de problemas reagrupados en un impresionante zoológico.
Las clases más importantes se llaman P, NP, y PSPACE (las siglas son las abrevaciones de Polynomial time, Non deterministic Polynomial time y Polynomial SPACE) :

• La primera, P, es la clase de problemas que una máquina puede resolver en un tiempo polinomial del tamaño de los datos que le han sido entregados : grosso modo, es la clase de los problemas fáciles de resolver.

• La segunda, NP, es la clase de problemas en los cuales una máquina puede verificar una solución en tiempo polinomial del tamaño de los datos.

• La tercera, PSPACE, es la clase de problemas que una máquina puede resolver utilizando un espacio memoria polinomial del tamaño de los datos.

Los especialistas tratan de comprender las relaciones entre esas diferentes clases. En lo referente a esas tres, hay inclusiones.

• Primero, P está contenido en NP ; en otras palabras, si usted sabe resolver un problema, sabe también verificar una solución.

• Del mismo modo, P está contenido en PSPACE ; en el modelo de las máquinas Turing, tanto como en un verdadero computador, toma un poco de tiempo acceder a una unidad central de procesamiento (CPU)... Por lo tanto, en un tiempo polinomial del tamaño de los datos, una máquina puede acceder solo a un espacio memoria de tamaño polinomial.

• De hecho, NP mismo está contenido en PSPACE ; si se sabe que un problema dispone de una prueba verificable en tiempo polinomial, se puede escribir sucesivamente cada prueba potencial, mirar si es una y, si no, pasar a la siguiente. El punto es que en cada etapa se puede reutilizar el mismo espacio de memoria para verificar si la nueva ’’prueba’’ es en realidad una.

El asunto crucial del asunto es saber si P es igual a NP : si un problema dispone de una solución rápidamente verificable ¿se puede adivinar rápidamente esta solución ? Los especialistas por supuesto piensan que no, pero nadie tiene la prueba...

Pruebas interactivas

Como ya lo he dicho, la teoría de la complejidad introduce la noción de prueba interactivas. Ella nombra IP (por Interactive Polynomial time) a la clase de los problemas que poseen una prueba interactiva corta.

Precisamente, un problema pertenece a IP si se puede encontrar dos máquinas, un ’’probador’’ y un ’’verificador’’. El probador da la respuesta al problema. Para esto, acepta someterse a una serie de preguntas del verificador. Si la solución es correcta, el probador debe responder convenientemente con probabilidad 1 ; si no, solo puede responder con una probabilidad < 1. Además, si el probador puede utilizar una potencia de cálculo ilimitada, el verificador dispone sólo de un tiempo polinomial.

Los problemas NP pertenecen evidentemente a IP : si usted tiene una prueba corta, puede dársela al verificador para que la procese en tiempo polinomial. Pero si no, los problemas típicos que pertenecen a IP son de naturaleza negativa : demostrar que dos grafos no son isomorfos, que un entero no es un residuo cuadrático... o que dos calcetines son de diferente color.

En el ejemplo de este texto, mis hijos eran el probador y yo era el verificador : Si los calcetines hubieran sido del mismo color, ellos habría tenido solo una oportunidad sobre dos para responder correctamente, pero como los calcetines eran de colores diferentes (y los niños no son daltónicos...) ellos pudieron responder correctamente cada vez..

Uno de los resultados espectaculares relativos a las pruebas interactivas es el teorema de Adi Shamir (1992) : la clase IP es igual a la clase PSPACE. En otras palabras, si un problema requiere sólo de un espacio memoria polinomial para ser resuelto, será posible imaginar un protocolo que certificará la respuesta en tiempo polinomial..