Conceptos y limitaciones que un programador debe conocer

Para muchos de nosotros programadores, es muy divertido y retador darle una secuencia de órdenes finita a una computadora con el fin de ofrecer una solución totalmente funcional a nuestros clientes o empleadores. Pero, debemos tener muy en cuenta que existen algoritmos los cuales son computacionalmente intratables, es decir, que una computadora tardaría años en resolver para un conjunto de datos relativamente grande.

Como ejemplo, para responder a la pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visitas cada ciudad exactamente una vez y regresas a la ciudad origen? Implica resolver uno de estos algoritmos conocido como el problema del vendedor ambulante (del inglés TSP) y se sabe que este problema no puede resolverse de una forma eficiente, ya que el mejor algoritmo conocido es de carácter exponencial; por ejemplo, si pensáramos analizar todos los posibles caminos sucedería esto: para 5 ciudades hay 12 rutas diferentes, pero: 

• Para 10 ciudades hay 181.440 rutas diferentes.
• Para 30 ciudades hay más de 4·10³¹ rutas posibles. Un ordenador que calcule un millón de rutas por segundo necesitaría 10¹⁸ años para resolverlo. Dicho de otra forma, si se hubiera comenzado a calcular al comienzo de la creación del universo (hace unos 13.400 millones de años) todavía no se habría terminado.

Entonces, ¿cómo le hace Google Maps para darnos rutas con tanta rapidez? Bueno, la respuesta es sencilla, la pregunta compleja se convierte a una más sencilla utilizando probabilidad, es decir para el caso de TSP en lugar de intentar obtener el camino más corto, se intenta obtener uno de los más cortos.

El problema TSP es conocido como un problema NP-completo, ¿qué significa esto?

P versus NP es conocido como uno de los 7 problemas del milenio. Todos los programadores siempre nos hemos preguntado en algún momento, ¿cuál será el algoritmo más eficiente pare resolver este problema? Bueno pues una gran comunidad de científicos ha ido madurando esta pregunta y se han creado grupos de algoritmos, en particular, los algoritmos P son todos aquellos cuya complejidad o cantidad de instrucciones requeridas puede expresarse mediante un polinomio; por ejemplo, realizar una multiplicación de matrices de n x n es n³, lo cual es un polinomio. Los algoritmos NP son por el contrario aquellos que no se pueden expresar de manera polinomial, pero su verificación sí tiene un costo polinomial; por ejemplo, el TSP tiene complejidad n! o en los mejores casos n²2ⁿ donde n es la cantidad de ciudades, esta complejidad no puede expresarse de manera polinomial, sin embargo, una vez dado el camino más corto, verificar que lo sea es sencillo y su complejidad puede ser expresada a manera de polinomio.

Resolver la pregunta ¿NP=P? Es sin duda uno de los problemas más polémicos del momento, esto equivaldría a responder: ¿Todo problema que se puede verificar en tiempo polinomial también puede resolverse en tiempo polinomial? Las implicaciones son enormes; si la respuesta es sí, todos los métodos criptográficos actuales usados para mantener la información segura en internet se vendrían abajo, ya que usan esta premisa haciendo que sea fácil la generación de texto cifrado (P), pero difícil la extracción del texto original a partir del cifrado (NP). Por otro lado, si la respuesta es que no son iguales, simplemente nos llevaríamos una enorme decepción al saber que existen problemas, los cuales por más que intentemos no podremos mejorar sus tiempos de ejecución.

Ahora bien, los problemas NP-completos son los problemas que representan a toda la clase NP, es decir que todo problema NP puede ser convertido en tiempo polinomio a uno NP-completo, los problemas NP-completos tienen como fin ayudar a resolver si NP=P, ya que basta con demostrar que uno de los problemas NP-completos tiene una solución con complejidad polinomial para demostrar que todos los NP tienen una solución polinomial, ya que si es así todos los NP podrían convertirse a ese problema NP-completo y como ambos tendrían complejidad polinomial, la suma de sus complejidades también sería polinomial.  El Clay Mathematics Institute premia a aquel que resuelva este problema o alguno de los otros 6 con la suma de un millón de dólares cada uno.

Algo más, alguna vez has pensado, ¿cuántos problemas son programables? Si lo has hecho, te tengo malas noticias, las tesis de Church y Turing se unen para decirnos que solo existe una cantidad infinita y contable de problemas que pueden resolverse a manera de algoritmo. ¡Efectivamente son muchos algoritmos, pero desgraciadamente existe otra cantidad incontable de problemas que no pueden ser resueltos! Ejemplo: obtener el ultimo dígito de Pi.  Y si lo pensamos un poco más nos daremos cuenta de la increíble cantidad de problemas que no pueden ser programados.

Podemos darnos cuenta la gran cantidad de teorías matemáticas detrás de esta profesión tan interesante que es el desarrollo de software, pero ya que estamos hablando de limitaciones pensemos también en las matemáticas.

Lo que quizá muchos nos hemos preguntado es: si todo está basado en las matemáticas, ¿en qué se basan las matemáticas? Bueno las matemáticas son una teoría axiomática, es decir que es una teoría que comienza con una serie de reglas tomadas por hecho y en base a ellas se construyen nuevos teoremas aún más complejos. Pero eso no evita que se piense en formalizar las matemáticas, la formalización más aceptada es sobre la teoría de conjuntos, es decir, el 1 representa el conjunto con cardinalidad 1 (es decir que contiene un elemento) y así sucesivamente. Quien no recuerda con esto a su profesor de primaria explicando una suma con manzanas (un conjunto de manzanas), pues es básicamente la misma idea, pero dar una explicación a operaciones numéricas como suma, resta multiplicación, división, usando teoría de conjuntos.  

Bueno pues todo iba bien hasta que Russell formuló la siguiente paradoja: ¿El conjunto de los conjuntos que no forman parte de sí mismos forma parte de sí mismo?  Si comienzas suponiendo que sí, entonces el conjunto tendría un conjunto que forma parte de sí mismo y contradice la pregunta y si supones que no entonces es un conjunto que no forma parte de sí mismo y por lo tanto forma parte de sí mismo. Confuso, pero demuestra que la teoría de conjuntos es inconsistente, es decir, que hay cosas que son verdaderas y ciertas a la vez. Esto fue catastrófico para las matemáticas que estaban fundamentadas en la teoría de conjuntos, pero con el tiempo se demostró algo aún más triste, Gödel en sus teoremas de incompletitud demuestra que toda teoría axiomática está condenada a ser incompleta o inconsistente, es decir, que no se podrá probar todo o en su defecto habrá cosas que son verdaderas y falsas a la vez. En el caso de las matemáticas suceden las dos cosas, ya que se han encontrado preguntas las cuales no son resolubles con las matemáticas actuales y Russell nos demuestra con su paradoja que también son inconsistentes.

Conclusión: conceptos y limitaciones de programación

Con estas ideas tan interesantes nos damos cuenta de que hay aún demasiado por descubrir y la computación juega un enorme papel en ello. Además, nos ayuda a comprender por qué han crecido las nuevas tendencias del uso de algoritmos probabilistas y de aprendizaje automático, los cuales ayudan a obtener aproximaciones a resultados que hubiéramos tardado años en obtener si lo intentáramos de manera determinista.

Referencias: The P=NP Question and Gödel’s Lost Letter, Lipton, Richard J; Wikipedia; Computational Complexity: A Modern Approach By Sanjeev Arora, Boaz Barak.