Los problemas del milenio: ¿P = NP?
Alfonso Ruiz
El problema más importante de la Teoría de la Computación es la pregunta siguiente:
¿La clase de problemas de decisión que puede resolver una computadora de manera eficaz es más pequeña que la clase de los problemas de decisión cuyas soluciones puede verificar de manera eficaz?
A lo largo de este texto daremos una explicación detallada de los términos en negritas en la pregunta anterior, los cuales corresponden a definiciones matemáticamente técnicas. Es importante mencionar que existen distintas maneras equivalentes de formular este problema y a lo largo de este texto hablaremos sobre la descripción formal del problema.
Con ello buscamos que el gran público interesado en las matemáticas y la ciencia de la computación tenga una comprensión detallada de uno de los problemas abiertos más fascinantes en la actualidad.
- Los 7 problemas del milenio
- Importancia en Ciencia de Datos
- Ejemplo: el juego del Buscaminas
- Problemas de decisión
- Computabilidad
- Eficacia computacional
- Verificación de soluciones
Los 7 problemas del milenio
En el Congreso Internacional de Matemáticas del año 1900 el matemático David Hilbert anunció una lista de 23 problemas que desde su punto de vista eran los más importantes para las matemáticas.
Uno de los aspectos más polémicos de esta lista es que Hilbert insinuó que una vez resueltos estos problemas las matemáticas de alguna manera estarían terminadas. Afortunadamente esto no ocurrió pues aunque una buena parte de los problemas propuestos por Hilbert han sido resueltos, los matemáticos han encontrado una nueva lista de problemas fundamentales tanto para las matemáticas como para sus interacciones con otras áreas como la física, la ingeniería o la computación.
En el año 2000 el Clay Institute of Mathematics anunció una lista con 7 problemas a los que llamó los problemas del milenio. A continuación les presentamos un breve video sobre los puntos más generales.
En el Colegio de Matemáticas Bourbaki estamos presentando una serie de vídeos y artículos con el objetivo de explicarle al gran público la importancia y los detalles de estos problemas. Este artículo corresponde a nuestra explicación sobre uno de los 6 problemas aún sin resolver, hasta el momento la Conjetura de Poincaré es el único de los problemas que ha sido resuelto.
Por el otro lado, en una entrada anterior de nuestro boletín Bourbakisme hablamos brevemente sobre cómo recientemente los Operadores Neuronales de Fourier han influido en otro de los problemas del milenio, pronto dedicaremos una edición a este problema fundamental en ingeniería y física de fluidos.
Importancia para la Ciencia de Datos
Más adelante explicaremos los detalles de la pregunta ¿P = NP? sin embargo podemos adelantar que a pesar de haber incluido la palabra eficacia en el enunciado inicial, esta hace referencia a un concepto teórico y no a algoritmos concretos, por lo tanto sin importar cuál sea la respuesta correcta a ¿P = NP? esta difícilmente arrojará nuevos algoritmos que puedan solucionar problemas dentro de Ciencia de Datos.
Para enfatizar, la ciencia de datos es una disciplina que depende inevitablemente de otras áreas, en este caso nosotros destacaríamos las siguientes:
- Tecnológica: con esto nos referimos a la creación de hardware y software veloz y fácil de utilizarse, esto incluye el desarrollo de tarjetas gráficas, arquitecturas de bases de datos polivalentes, clouds seguras, etc.
- Científica: aquí es donde las matemáticas son una herramienta fundamental que nos permite describir en un lenguaje formal los problemas que deseamos solucionar (métricas de nuestros modelos por ejemplo) y las propuestas para solucionarlos (algoritmos o modelos, pensemos en todos los esfuerzos relacionados con las arquitecturas y métodos de entrenamiento de las redes neuronales).
- Cultura data-driven: con esto nos referimos a una interpretación responsable de los resultados que arrojan los modelos, es imposible realizar exitosamente un análisis de datos o entrenar un modelo de forecast sin comprender cabalmente el problema que deseo resolver.
Considerando lo anterior, si nos preguntamos cuál es la importancia de resolver el problema ¿P = NP? pronto concluiremos que esto no es una prioridad para los científicos de datos, por lo menos no en su día a día.
Así como ¿P = NP? existen muchos otros problemas abiertos, teoremas y objetos matemáticos cuya importancia en el quehacer de un científico de datos podría ser menor a saber manejar bases de datos (por ejemplo), sin embargo desde el Colegio de Matemáticas Bourbaki luchamos por promover una cultura matemática dentro de esta disciplina. Esta cultura matemática podría compararse con otras como la alfabetización financiera en el mundo empresarial o el conocimiento de las implicaciones éticas en inteligencia artificial.
Uno de nuestros cursos llamado Matemáticas para la Ciencia de Datos está dedicado precisamente a enseñar a los practicantes e incluso a los expertos en el uso de algoritmos de Machine Learning, las sutilezas matemáticas escondidas detrás de las bibliotecas o software que utilizan.
En otro de nuestros cursos Machine Learning & AI for the Working Analyst los estudiantes encontrarán una introducción enfocada en los modelos de Machine Learning y cómo utilizarlos para resolver problemas industriales o de negocio.
Ejemplo: el juego del Buscaminas
Antes de comenzar a describir formalmente los términos técnicos utilizados para enunciar de ¿P = NP? vamos a comenzar con un ejemplo que muchos de los lectores podrían estar familiarizados, el problema del buscaminas.
A continuación compartimos con ustedes una breve descripción de este juego así como su relación con ¿P = NP? Sugerimos al lector que tenga este ejemplo en mente en el resto del texto.
Problemas de decisión
De manera informal un problema de decisión es un conjunto de instrucciones que en un principio pueden o no ser seguidas por un agente, resolver un problema de decisión equivale a encontrar un algoritmo que le permita al agente seguir estas instrucciones satisfactoriamente. En la siguiente sección hablaremos de aquellos agentes que más nos interesan: las computadoras.
De manera formal, un problema de decisión al que llamaremos L es un conjunto de instrucciones que podemos escribir en algún alfabeto, normalmente en ciencias de la computación el alfabeto que utilizaremos será el de los bits, a cadenas arbitrariamente grandes (pero finitass) de 0's y 1's. De esta forma un problema de decisión es una familia de cadenas en el alfabeto de los bits.
Cada uno de estos vectores pueden representar lo siguiente:
- Números enteros: es bien sabido que cualquier número entero puede escribirse utilizando su representación binaria.
- Funciones entre números enteros: para esto es necesario notar que una función es una familia de parejas ordenadas de números enteros. Las parejas ordenadas pueden representarse dentro de este alfabeto pues hemos incluido símbolos para las comas o los paréntesis.
- Operaciones en general entre números enteros: las operaciones binarias por ejemplo son tripletas de números, las cuáles también están dentro de nuestro lenguaje por la misma razón que el punto anterior.
Computabilidad
La definición de lo computable es quizás una de las más delicadas matemáticamente, para este punto es necesario hacer referencia a uno de los trabajos más formidables del siglo XX, a saber el descubrimiento por Alan Turing del ADN de la computación, en el siguiente vídeo compartimos algunos puntos importantes.
Si un problema de decisión es una familia de cadenas en el alfabeto de los bits, diremos que un problema de decisión es computable cuando exista una Máquina de Turing que pueda calcular todas sus instrucciones y podamos garantizar que en un tiempo finito esta máquina arrojará un resultado final positivo.
Eficacia computacional
Alan Turing no consideró dentro de su definición de problemas de decisión computables una restricción respecto al tiempo de parada de una máquina. Para definir correctamente lo que significa ser eficaz es necesario introducir la clase de los problemas de decisión P. Los problemas P no siempre deberán de ser sencillos, ellos podrán ser muy complicados sin embargo la única razón que permitiremos para que sean complicados es porque corresponden a cadenas muy largas.
Formalmente problema de decisión es un conjunto de cadenas computable tal que existe la siguiente garantía siguiente, el tiempo de parada de la máquina de turing que lo convierte en un problema complicado es una función polinomial que depende únicamente de la longuitud de las cadenas que lo definen.
Verificación de soluciones
Antes de definir la clase de los problemas NP es necesario realizar la siguiente observación: si suponemos que un problema es P y proponemos una máquina de Turing que sigue un algoritmo particular para solucionarlo, entonces el problema de verificar si este algoritmo es correcto consiste únicamente en seguir las instrucciones, si la máquina de Turing no se detiene entonces significa que la solución no es correcta. De esta manera hemos argumentado por qué la clase P está contenida en la clase NP.
De manera formal un problema de decisión será NP cuando para todo algoritmo, exista una máquina de Turing que pueda solucionar el problema de decisión de si ese algoritmo efectivamente garantiza que el problema inicial es computable.
Oferta académica
- Track de Ciencia de Datos. (49 semanas).
- Machine Learning & AI for the Working Analyst ( 12 semanas).
- Matemáticas para Ciencia de Datos ( 24 semanas).
- Especialización en Deep Learning. (12 semanas).
- Track de Finanzas Cuantitativas (49 semanas)
- Aplicaciones Financieras De Machine Learning E IA ( 12 semanas).
- Las matemáticas de los mercados financieros (24 semanas).
- Deep Learning for Finance (12 semanas).
