Notícias

El problema que los informáticos no han podido resolver en 45 años

EL PAIS, 22 de mayo de 2017. La pregunta "¿P=NP?" trae de cabeza a los programadores desde 1971. ¿Qué diantres se esconde tras la pregunta '¿P=NP?', y por qué parece ser tan importante para los informáticos? Se trata de una pregunta, todavía sin respuesta desde 1971, año en que fue planteada, que trae de cabeza a los informáticos. Si fuera P≠NP, las cosas seguirían más o menos igual, pero si fuera P=NP, entonces muchas cosas cambiarían y no necesariamente para mejor. Veamos por qué.

22 de mayo de 2017

Ricardo Peña Marí · 22 MAY 2017 - 20:00 CEST.

Muchas personas se preguntan qué diantres se esconde tras la pregunta ¿P=NP?, y por qué parece ser tan importante.

Se trata de una pregunta, todavía sin respuesta desde 1971, año en que fue planteada, que trae de cabeza a los informáticos. Si fuera P≠NP, las cosas seguirían más o menos igual, pero si fuera P=NP, entonces muchas cosas cambiarían y no necesariamente para mejor. Veamos por qué.

Gran parte de la ciudadanía tiende a pensar que los computadores pueden resolver todos los problemas, y que los que no pueden resolver hoy, podrán hacerlo mañana, porque su potencia de cálculo crece continuamente.

Los informáticos sabemos en cambio, que una infinidad de problemas de cómputo no tendrán solución nunca (los llamamos problemas indecidibles), y que para otros problemas existen algoritmos que los resuelven, pero empleando para ello tanto tiempo de cálculo, que a efectos prácticos es como si fueran irresolubles (los llamamos problemas intratables).

Los problemas que resuelven los computadores en un tiempo razonable los llamamos polinomiales, y todos ellos se agrupan en la llamada clase P. Se dicen así porque su tiempo de cómputo está descrito por un polinomio en el tamaño de los datos. Por ejemplo, el problema de multiplicar dos matrices de n filas y n columnas se puede resolver utilizando menos de n3 multiplicaciones. Ninguno de los problemas intratables está en la clase P.

Hay otra clase de problemas, a la que llamamos NP, cuya definición está hecha de tal manera que incluye todos los problemas de la clase P, pero también otros muchos que se comportan de un modo intrigante. Uno de esos problemas es el llamado problema del viajante de comercio.

Más información : P=NP EL PAIS 20170522



Volver a la página anterior