LA PREGUNTA "¿P=NP?" TRAE DE CABEZA A LOS PROGRAMADORES DESDE 1971
El problema que los informáticos no han podido resolver en 45 años
22 de mayo de 2017 (06:25 h.)
¿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é.
Hay otra clase de problemas, a la que llamamos NP. Uno de esos problemas es el llamado problema del viajante de comercio: dado un mapa de carreteras, consiste en encontrar el camino más corto para visitar n ciudades una sola vez y volver al punto de origen. Para estos nuevos problemas de la clase NP, los mejores algoritmos que se conocen tienen un coste similar al de los problemas intratables, pero nadie ha demostrado que no existan algoritmos polinomiales para ellos.
La parte buena de ello es que podríamos resolver, en tiempos cortos, problemas del viajante con miles de ciudades y otros cientos de problemas útiles para los que hoy tenemos algoritmos muy costosos, y eso sería beneficioso para la industria, las comunicaciones y el desarrollo en general. La parte mala es que las claves criptográficas se descifrarían con gran facilidad, y muchas cuentas bancarias y comunicaciones cifradas quedarían expuestas a los amigos de lo ajeno.