Matemática Discreta

Si os acordais allá por la EGB os enseñaron un método para calcular raíces cuadradas (los que hayan pasado por la ESO no sé si os lo habrán enseñado o no; haber nacido antes ;) ). Era un método bastante engorroso; tanto que ya nadie nos acordamos de él, pero el caso es que existe un método. Sin embargo, la operación inversa (es decir, elevar un número al cuadrado) es mucho más fácil, una simple multiplicación.

Suponed ahora que alguien os pide que comprobeis si el número A es la raíz cuadrada de B. Podeis calcular la raíz de B (que hemos quedado que es un proceso lento), o podeis comprobarlo de otra manera: elevando A al cuadrado (que es más rápido).

Este ejemplo lo que pretende ilustrar es el hecho de que para algunos problemas, comprobar una solución es más rápido que encontrarla.

Por supuesto, cuando digo "rápido", es algo que depende de cómo de grandes sean los datos de mi problema: calcular el cuadrado de un número de 20 cifras lleva más tiempo que hacer lo propio para un número de 2 cifras. Por eso, el concepto de "rápido" no es un valor numérico, sino una función. Esta función nos dice cómo crece el número de pasos a dar cuando crece el tamaño de los datos. Por ejemplo, para sumar dos números de n cifras, tenemos que dar aproximadamente 2n pasos (sumar las cifras correspondientes, y tal vez una que nos llevamos de la suma anterior). Por lo tanto diremos que la complejidad de la suma será 2n (en realidad hay métodos más rápidos, pero para hacernos una idea nos vale con esto). Del mismo modo, podemos calcular la complejidad de la multiplicación, de la raíz cuadrada, o de la función que sea como el número de pasos elementales que hay que dar para calcularla para un número de n cifras (o dos números de n y m cifras si es el caso).

Notar que cuando definimos la complejidad de una función, lo hacemos suponiendo que tenemos un método concreto para calcularla. Si hubiera otros métodos, habría otras complejidades. Normalmente cuando hablamos de la complejidad de una función, nos referimos a la del método más rápido que conocemos para calcularla. Sin embargo, casi nunca sabemos si existe otro método más rápido que no conozcamos.

Pues bien, con estos tres párrafos anteriores tenemos los ingredientes para entender uno de los principales problemas abiertos en la matemática actual: ¿P=NP?

Y antes de que pongais caras raras os voy a explicar que significa eso de P y NP:

P es el conjunto de problemas que se pueden resolver en tiempo polinomial (es decir, más rápido que n^a para algún a). En concreto la suma, la multiplicación y casi todas las operaciones habituales son de este tipo (y es razonable, porque esta es la clase de problemas más sencillos). Intuitivamente, podemos decir que un problema está en la clase P si se puede resolver "rápidamente". Y cuando digo "rápidamente" para referirme a "en tiempo polinomial", es por una cuestión de experiencia empírica: los métodos que funcionan en tiempo polinomial normalmenete no requieren grandes potencias. En la práctica, "tiempo polinomial" quiere decir "poco tiempo", mientras que "tiempo no polinomial" quiere decir "tanto tiempo que es inviable".

NP es, en cambio, el conjunto de los problemas que se pueden comprobar en tiempo polinomial. Es decir, la solución se puede calcular rápidamente o no, pero si me dan un candidato a solución, sé decir de una forma rápida si realmente es una solución o no. Viene a ser lo que la raíz cuadrada en el ejemplo anterior: calcularla es un proceso lento, pero si me dan un candidato sé calcular en poco tiempo si es la solución que busco o no (en realidad, la raíz cuadrada sí que está en P; lo que pretendo ilustrar es la diferencia entre calcular la solución y comprobar una posible solución).

Evidentemente, si sé calcular una solución rápidamente, sé comprobar soluciones rápidamente (basta con compararlas con la solución encontrada), por lo tanto P es un subconjunto de NP. Pero y al revés? Es decir: si tengo un problema tal que sé comprobar rápidamente si algo es una solución, sé calcular una solución de forma rápida? Pues si sabeis dar una respuesta a esta pregunta os podeis ganar un millón de dólares, que es el premio que el instituto Clay ofrece a quien resuelva esta cuestión (a parte de haceros famosísimos en el mundillo de la teoría de la complejidad).

Esto es todo de momento, ¿alguna pregunta?