Apuntes de complejidad computacional

Abstract

La solución de problemas de toda índole requiere dedicar suficiente esfuerzo para conocer lo más posible del “enemigo” que se enfrenta. La mayoría de los problemas de optimización presentan características de complejidad que los puede hacer difíciles o aún imposibles de resolver en tiempos razonables. Sin embargo, conociendo un poco más de su naturaleza, recovecos y misterios, se logra desarrollar estrategias poderosas para atacarlos y vencerlos. Este libro introduce al conocimiento necesario para poder someterlos diseñando estrategias de solución, es decir, la Complejidad Computacional. El libro aborda temas como la medida de dificultad de problemas, algoritmos de solución eficientes, la definición de problemas polinomiales deterministas y no deterministas, y técnicas de reducciones y transformaciones entre problemas. En la aventura de resolver problemas de optimización, un principio esencial es que: “conocimiento mata esfuerzo computacional”.