“P vs NP”: Las matemáticas que nos dicen cómo de difícil es un problema | Café y teoremas

0


P vs NP, central en el campo de la teoría de la complejidad computacional, es uno de los siete problemas del milenio seleccionados por el Clay Institute y su resolución es premiada con un millón de dólares.

Los ordenadores están cada vez más presentes en nuestra vida diaria y nos ayudan a realizar numerosas actividades, como encontrar la ruta más corta a un destino. Afortunadamente, existen algoritmos bien conocidos para resolver de manera eficiente muchos de estos problemas prácticos. Sin embargo, para muchos otros problemas relevantes, no se conoce un algoritmo que ofrezca una respuesta correcta en un tiempo razonable y no se sabe si es posible que exista, aun cuando sea posible verificar, de manera sencilla, que un La posible solución es incorrecta.

Considere, por ejemplo, un gráfico, es decir, una estructura matemática que consta de vértices (puntos) conectados por aristas (líneas). En un gráfico, un camino es una forma de ir de un punto a otro siguiendo a sus artistas. Un problema sería determinar si en cada gráfico hay o no un camino que pasa por cada arco una vez y solo una vez – llamado camino de Euler -. Existe un algoritmo para resolver esta cuestión. eficiente que de hecho, si es así, encuentra el camino de Euler.

En teoría de la computación, un algoritmo es eficiente si se realiza en un tiempo proporcional en «forma polinomial» al tamaño del problema inicial. Por ejemplo, en nuestro caso, si norte es el número de vértices del gráfico y el tiempo que tarda el algoritmo en encontrar la solución se expresa como un polinomio de norte, p.ej, norte² o 2norte+ 7, es eficiente; si el tiempo tiene una forma no polinomial, como 2n, no es eficiente.

Camino hamiltoniano

Modifiquemos un poco la pregunta anterior: ahora queremos saber si, en una gráfica dada, hay un camino que pasa por cada vértice y lo hace una sola vez, lo que se llama camino hamiltoniano. Un algoritmo simple para resolver este problema sería verificar todos los caminos posibles del gráfico y ver si hay hamiltonianos. Si el gráfico inicial tiene cuatro vértices, entonces se deben analizar 24 caminos posibles, o la mitad de ellos, usando simetría, lo cual es factible. Pero si tomamos un gráfico de 30 vértices, el número de posibles caminos a estudiar es mayor que el número de microsegundos, una millonésima de segundo, estimado desde el Big Bang. En la práctica, este problema no tiene solución.

Se podría pensar que, utilizando algún truco, como el que se utilizó para resolver el problema de la ruta de Euler, sería posible diseñar un algoritmo más eficiente que el anterior. Desafortunadamente, a pesar de la gran cantidad de trabajo invertido en el tema, por el momento no se conoce ningún algoritmo sustancialmente más eficiente que el indicado. Sin embargo, si alguien afirma tener un camino hamitoniano para el gráfico de 30 vértices, es fácil verificar, incluso a mano, que realmente lo es.

Todos los problemas en los que es fácil verificar que una posible solución es correcta pertenecen a la clase NP, que incluye tanto el problema del camino de Euler como el problema del camino hamiltoniano. Esta clase incluye otra, denominada P, formada por problemas cuya solución se puede obtener mediante un algoritmo eficiente, como el problema de la ruta de Euler. Aunque sabemos que P está incluido en NP, actualmente se desconoce si estas dos clases son iguales, es decir, no sabemos si todos los problemas de NP se pueden resolver con un algoritmo eficiente (que quizás no sepamos por el momento). Esta pregunta se llama el problema P vs NP.

La pregunta, central en el campo de la teoría de la complejidad computacional, es uno de los siete problemas del milenio seleccionados por el Instituto Clay y su resolución es premiada con un millón de dólares.

Daniel Graça, profesor de la Universidad del Algarve

La pregunta, central en el campo de la teoría de la complejidad computacional, es uno de los siete problemas del milenio seleccionados por el Instituto Clay y su resolución es premiada con un millón de dólares. La opinión generalizada entre los expertos es que estas clases son diferentes, pero, a pesar de la gran cantidad de investigaciones desarrolladas sobre el tema, hasta el momento nadie ha podido demostrarlo.

Una de las estrategias utilizadas para abordar el problema desde la década de 1970 es confiar en problemas NP-completos que son, en cierto sentido, los problemas más difíciles de la clase NP. Un ejemplo de este tipo de problemas es el del camino hamiltoniano, pero existen muchos otros de diversa índole.

Lo interesante de este enfoque es que todos los problemas NP-completos son computacionalmente equivalentes, lo que significa que si pudiera encontrar un algoritmo eficiente para resolver cualquiera de ellos, sabría que puede resolverlos todos de manera eficiente, incluso el resto de los problemas NP. . , que son más simples y, por lo tanto, P sería igual a NP. Por el contrario, si se demostrara que un problema NP-completo no puede resolverse mediante ningún algoritmo eficiente, se determinaría que ninguno de ellos puede resolverse con dicho algoritmo y, por lo tanto, P sería diferente de NP.

A pesar de la promesa del enfoque, por el momento, parece que ni este ni ningún otro enfoque del problema ha sido suficiente para resolver P vs NP. De hecho, algunos resultados sugieren que nuestras herramientas matemáticas actuales no son lo suficientemente sofisticadas para abordar problemas como este.

En esencia, esta pregunta intenta determinar si es más difícil encontrar soluciones – qué se puede hacer en los problemas P – que verificar que un resultado es una solución correcta. Saber si este es el caso o no podría tener profundas implicaciones para las matemáticas y la ciencia en general.

Por ejemplo, podemos saber si es más difícil obtener una nueva demostración matemática que verificar que una determinada demostración es correcta. O si es más difícil formular una teoría que sea consistente con los datos experimentales disponibles que verificar la consistencia de una teoría dada. En general, creemos que este es el caso: la creatividad que requiere que se le ocurra una nueva prueba o teoría es más cara que la rutina de revisión. Sin embargo, si se demostrara que P = NP, tendríamos que cuestionar estas creencias. En cualquier caso, resolver el problema P vs NP tendrá un gran impacto tanto en el desarrollo de un nuevo tipo de matemáticas como en muchas aplicaciones prácticas.

Daniel Graça es un maestro de Universidad del Algarve e investigador de Instituto de Telecomunicaciones (Portugal).

Redacción y coordinación: Ágata A. Timón G Longoria (ICMAT).

Café y teoremas es un apartado dedicado a las matemáticas y el entorno en el que se realiza, coordinado por el Instituto de Ciencias Matemáticas (ICMAT), en el que investigadores y miembros del centro describen los últimos avances de esta disciplina, comparten puntos de encuentro entre las matemáticas y otros sociales y expresiones culturales y recordemos a quienes han marcado su desarrollo y han sabido transformar el café en teoremas. El nombre evoca la definición del matemático húngaro Alfred Rényi: «Un matemático es una máquina que transforma el café en teoremas».

Puedes seguir a la MATERIA en Facebook, Gorjeo Y Instagram, o regístrese aquí para recibir nuestro boletín semanal.



También podría gustarte
Deja una respuesta

Su dirección de correo electrónico no será publicada.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More