## 3.1.1 PROBLEMAS ABSTRACTOS

Para comprender la clase de problemas solucionables en el tiempo polinomial, primero debemos tener una noción formal de lo que es un "problema". Definimos un problema abstracto Q como una relación binaria en un conjunto I de instancias de problema y un conjunto S de soluciones de problema.

Todos los problemas –en la vida como en ciencia– pueden dividirse en dos grupos principales, así: como problemas indecidibles y como problemas decidibles. La decibilidad de un problema hace referencia al famoso décimo problema formulado por D. Hilbert en el Congreso Mundial de 1900 (Gray, 2006), conocido como el problema de detención (Haltungsproblem).

Un problema se dice que es indecidible cuando no existe un algoritmo que permita resolver un problema dado, incluso dados tiempo y recursos ilimitados. En consecuencia, no es posible determinar si dicho problema a) se detiene, ni b) cuándo se detiene. La ausencia de cualquier algoritmo aquí significa que el problema no puede ser abordado ni resuelto, básicamente, con la ayuda de fórmulas, reglas, procedimientos, normas o “recetas” ya conocidas y probadas anteriormente, y ni siquiera con cualesquiera otra susceptibles de ser desarrolladas en el futuro. Ejemplos conspicuos de esta clase de problemas indecidibles son: la vida misma, la salud, la equidad, la pobreza, el conocimiento. Los límites de la computación y la lógica conocidas da pie para que pueda pensarse, como es efectivamente el caso, en otros tipos de computación distintos a los conocidos y que se basan en la arquitectura de Von Neumann y en la tesis Church-Turing. Los dos tipos más factibles de computación son la hipercomputación y la computación cuántica. No en última instancia, lo que se encuentra detrás de este tipo de problemas son los retos propios de la criptografía, uno de los capítulos más apasionantes tanto de la computación, las matemáticas y la lógica como de las ciencias de la complejidad.

Un problema se dice que es decidible, por contraste con los indecidibles, cuando existe un algoritmo para su resolución. En otros términos, un problema indecidible es aquel que no se sabe o se puede llegar a saber: a) si se detiene, o bien b) cuándo se detiene. Con base en Hilbert y en la teoría de la computación, esto hace referencia al famoso problema de la detención (Haltungs-problem). Incluso, desde otra perspectiva, un problema es decidible cuando es compresible; la compresibilidad hace referencia a un algoritmo o fórmula en el que un problema, lenguaje o programa puede ser condensado, reducido, comprimido o expresado. Por contraste, los problemas indecidibles son incompresibles.

Los problemas decidibles se dividen en dos: los problemas P y los problemas NP. P significa que el problema es polinomial; es decir, se trata de todos aquellos problemas que pueden ser abordados y resueltos descomponiendo el problema en los términos que componen al problema considerado. Incluso, de una manera más precisa, es posible decir que los problemas P se abordan y se resuelven en un tiempo polinomial.

Por su parte, los problemas NP son todos aquellos que son no-polinomiales y que, en consecuencia, ni se abordan ni se resuelven descomponiendo los mismos en los términos que los componen. Y sin embargo, esta clase de problemas se resuelven y deben resolverse en un tiempo polinomial, esto es, en el tiempo práctico que caracteriza a todas las actividades normales de los seres humanos.

###