Otro millón de dólares te espera: ¿Es P = NP?

Por supuesto todo eso no son las ocupaciones a las que se dedican los matemáticos que investigan. Ni siquiera eso son “problemas”, sino ejercicios rutinarios para verificar si se han comprendido algunos conceptos, si se sabe aplicar ciertas fórmulas o si se ha adquirido la destreza suficiente para poner en práctica un determinado algoritmo (cadena de operaciones, no exclusivamente aritméticas, que nos llevan a un determinado fin: la base de la programación en informática; en un momento volveremos sobre este concepto).

Entre los ejercicios, tampoco todos son del mismo nivel de dificultad. Diferentes autores han establecido clasificaciones que miden esa dificultad de acuerdo a distintos enfoques. Sin profundizar demasiado, por no alargarnos innecesariamente, digamos grosso modo que, en un nivel básico, nivel de reproducción , atendiendo a la denominación establecida por el Programa Internacional de Evaluación de los Alumnos (conocido por su acrónimo PISA, elaborado por la OCDE) para las tareas a efectuar en el aula con los alumnos, encontraríamos aquellas cuestiones en las que no es necesario hacer esfuerzo mental ninguno. Simplemente se aplica una determinada fórmula o concepto explicado en clase de forma mecánica. Por ejemplo, calcular el máximo común divisor de una serie de números, o resolver una ecuación de segundo grado, en la que a lo más nos dan desordenados sus términos.

Particularmente me gusta más decir nivel 0 , no en sentido peyorativo, sino como indicador de punto de partida, lo mínimamente exigible a un alumno para comprobar si ha entendido lo que se le ha explicado.

Un escalón por encima tendríamos tareas en las que haya que interpretar la información que tenemos, identificar y saber escoger elementos matemáticos conocidos para aplicarlos en la resolución, pero que no se nos explicitan de forma evidente. Sería un nivel de relación o conexión (nivel 1) . Algo así como lo que haría un fontanero o un albañil cuando se encuentra con una avería en un domicilio: observa la situación, detecta el posible problema, y selecciona las herramientas más adecuadas para solucionarlo. No utiliza un martillo para atornillar, por ejemplo, o unas tenazas para clavar una punta (salvo que como MacGyver no tenga nada mejor a mano, obviamente, pero no hablamos de casos límite). En nuestras clases estamos (mal)acostumbrados a utilizar exclusivamente ejercicios mecánicos como tarea para lograr adquirir este nivel de competencia matemática, pero es un error (bajo mi personal punto de vista; obviamente todo es opinable, pero luego se nos aburre el personal: lógico). Existen otro tipo de actividades, en las que hay que enfrentarse a un desafío real y concreto, existen juegos en los que hay que desarrollar y poner en práctica una estrategia, etc. A este nivel deberíamos aspirar a que todo alumno que pase por nuestras aulas llegue, un ciudadano que, en un futuro, sepa cómo aplicar las tres cositas que ha aprendido sobre porcentajes, por ejemplo, para que no le epate cualquiera que se presente en su casa ofreciéndole mejores coeficientes en el término variable del gas durante un cierto periodo de tiempo (meses de verano) que luego cuando ya se nos ha olvidado se modifica (invierno) precisamente cuando más consumimos (son varias y diferentes las tomaduras de pelo, y a veces, bastante sofisticadas, como para tomarse en serio echar un tiempo a hacer algún cálculo), o cómo elegir la oferta del producto telefónico que más nos conviene. Y ojo, en las situaciones reales, hay datos irrelevantes. Hay que saber cuál tomar y cuál no. Pero, ¿cómo se ponen los alumnos cuando en un ejercicio propuesto hay datos que no hay que utilizar porque sobran? ¡¡Ah, no, eso es ir a pillar!! Si no sirve que no se dé el dato, que nos confunden. Bueno, pues luego, volviendo atrás, no será capaz de decidir si coger la tenaza, el martillo o el destornillador (o sea, Pitágoras, Tales, o una sencilla regla de tres).

Finalmente, en un nivel 2 , nos encontramos con tareas y ejercicios en los que hay que dar un paso más, y utilizar nuestras neuronas de un modo más creativo; en éstas es necesario tomar alguna decisión. Lo denominan nivel de reflexión , y con él adquirido, seríamos capaces de justificar, argumentar porque así y no de otro modo, demostrar con corrección, etc. Los típicos ejercicios popularmente conocidos como “de idea feliz”, aunque por supuesto, tendríamos muchos grados para baremar el grado de intensidad y profundidad de la lucecita que se ha encendido para llegar a la resolución final. Serían los ejercicios como los que se proponen en las olimpiadas matemáticas, algunos bastante difíciles, aptos para aquellos que ya tienen claro que su futuro va a estar en una carrera de tipo científico. Ejercicios en los que profesores muy competentes pueden tener incluso dificultades para resolverlos, o directamente no ser capaces de hacerlo. Entre paréntesis, una de las, a mi juicio, mayores y mejores bajadas de humos al personal que existen es precisamente poder comprobar cómo un chaval de quince años puede resolver una cuestión que el más eminente catedrático universitario haya sido incapaz siquiera de vislumbrar (¿recuerdan la escena en 'El indomable Will Hunting '?). No ocurre constantemente, pero tampoco es raro. Una de las grandezas, insisto, a mi juicio, de las matemáticas y las ciencias en general. Ni que decir tiene que, si miramos a nuestro alrededor, a mucha gente tipo “usted no sabe con quién está hablando” le vendría de perillas como cura de humildad. ¿Será quizá ésta otra de las cosas impopulares de las matemáticas?

Bien, pues después de todo este prólogo, decir que los problemas a los que se enfrenta un matemático investigador están muy alejados aún de todos estos niveles. Un investigador en matemáticas tiene que desarrollar, demostrar, e idear, métodos y procedimientos quizá no existentes , que quizá no le lleven a ningún lado después de años de trabajo (pero muy importante, le sirven al resto de matemáticos posteriores que trabajen en ese problema para no repetir el mismo error de enfocar el asunto por ese camino) para tratar de lograr el objetivo de resolver el problema al que se enfrenta. Se han planteado muchas analogías para tratar de hacer entender a los demás cómo es enfrentarse a estos retos y cómo transmitir la satisfacción obtenida cuando se ha logrado el objetivo (en muy contadas ocasiones, por cierto; el que lo logra puede considerarse un verdadero héroe, una persona única, de un valor medible no con un millón de dólares, sino con nada que exista de tipo material). Algo así como alcanzar una cima jamás pisada por otra persona, o como abrir camino en un paraje inaccesible, o como poder iluminar un lugar en el que sólo nos podemos desplazar a tientas, sin ver absolutamente nada.

Teniendo en cuenta la naturaleza de este tipo de problemas, no es de extrañar que se haya baremado también el nivel de complejidad de dichos problemas. Una forma de hacerlo es tratar de estimar de algún modo el esfuerzo necesario para llegar a la solución. Tradicionalmente, y es una idea que han recogido las ciencias de la computación, consideramos un problema resuelto siempre que hemos encontrado un algoritmo, un procedimiento, para conseguirlo. Es un modo seguramente un tanto burdo o injusto (porque hay otros muchos factores a tener en cuenta), pero es un punto de partida que posteriormente podemos afinar. Y comprobar si dicho algoritmo es eficiente. Para considerarlo como tal, no sólo debemos considerar si con él se llega a la solución, sino si lo hace en un tiempo de ejecución relativamente aceptable. Si el tamaño de los cálculos crece “razonablemente” al aumentar el de los datos con los que trabajar, se puede considerar un procedimiento eficiente. Por ejemplo, si el número de pasos necesarios es proporcional a una potencia fija (el cuadrado, el cubo, en general x n , siendo x el tamaño de los datos de entrada). En ese caso, se dice que el problema es de clase P (tiempo de ejecución polinómico).

Sumar dos números de longitud k, por ejemplo, requiere de un tiempo para hacerlo proporcional a esa longitud. Se simboliza por O(k); multiplicar en cambio dos números de longitud distinta, k, l, con k>l, seria de orden O(k²) con el algoritmo que todos conocemos de la multiplicación (existen otros algoritmos que reducen ese tiempo de ejecución). En resumen, un problema es de tipo P cuando se puede resolver, porque conocemos un algoritmo que lo hace, en tiempo polinómico. Hay otros factores a tener en cuenta, como cuánta memoria es necesaria, etc., pero no lo liaremos más, al menos en esta ocasión.

Si el tamaño de los cálculos crece excesivamente (por ejemplo, exponencialmente), se considera que el algoritmo no es eficiente y el problema se cataloga como difícil. Esta idea no es del todo satisfactoria para evaluar la complejidad de un problema porque requeriría ver si cualquier algoritmo desarrollado para la solución es eficiente (y tendrían que incluirse los ya desarrollados, y los que en un futuro otros hicieran, y eso, es obviamente, imposible de saber). Así pues, la tarea de baremar la dificultad de un problema no es en absoluto trivial, y podría cambiar en un futuro.

Dentro de estos “problemas difíciles” hay varias subdivisiones, pero hoy sólo mencionaremos la clase NP . Serían aquello problemas que a día de hoy no podemos resolver (porque no hemos encontrado aún un algoritmo, etc., etc., etc.), pero para los que, conocida una solución particular, podríamos verificar que es correcta, que resuelve el problema, en tiempo polinómico. Hay cientos de problemas NP a día de hoy; por ejemplo, el famoso problema del viajante (al que dedicaremos una reseña algún día), el de la mochila (en una mochila de capacidad limitada, qué objetos seleccionar para llevar como necesarios, teniendo en cuenta que todos no caben), o el del buscaminas (podemos encontrar la solución de una situación concreta, pero no conocemos un algoritmo general que resuelva cualquier posición inicial).

Evidentemente todo problema P es NP (si se puede resolver con un algoritmo de forma general, se puede verificar cualquier solución particular), pero uno de los problemas del milenio (esos cuya recompensa es de un millón de dólares USA) es precisamente resolver la cuestión complementaria:

¿Es todo problema NP también un problema P, en cuyo caso P = NP? En otros términos, ¿será posible siempre encontrar un algoritmo eficiente que resuelva cualquier problema, o hay problemas para los que no existe algoritmo alguno que los resuelva? Casi, casi, un tema de futurología (¿cómo vamos a saber qué algoritmos se van a desarrollar en el futuro?). Por eso es tan complicado.

Lo que desde luego no es nada complicado, y es entretenido, es tratar de resolver las cuestiones planteadas para este verano en el XIV Concurso sobre Cine y Matemáticas del portal DivulgaMAT , y que un año más propone quien les habla. Uno de los objetivos es tratar de descubrir la película enigma de la que tratan las cuestiones, y volverla a ver (suele ser un clásico). No ganarán un millón de dólares, pero sí puede que algún libro interesante, y la satisfacción de encontrar la respuesta entre cientos de participantes, que es impagable. Este año es más sencilla que en otras ocasiones, así que anímense, y feliz verano a todos.

Alfonso Jesús Población Sáez es profesor de la Universidad de Valladolid y miembro de la Comisión de divulgación de la RSME.

El ABCdario de las Matemáticas es una sección que surge de la colaboración con la Comisión de Divulgación de la Real Sociedad Matemática Española (RSME).