Los problemas P vs NP tienen una grande variedad de campos en los que resultan altamente relevantes y pertinentes. Desde terrenos triviales, como el sudoku, hasta temas más sensibles computacional, lógica, matemática y militarmente hablando como la criptografía.
Queda dicho: los científicos, en el sentido amplio y más incluyente de la palabra, trabajan con problemas. No sobre “objetos” o a partir de “áreas o campos”. Se ha dicho que el paso más importante en la investigación consiste en formular o identificar problemas. Pues bien, esa es una condición necesaria, pero no suficiente para la buena ciencia.
Formulados de manera independiente por S. Cook, R. M. Karp y L. Levin entre 1971 y 1973, el problema —o los problemas P versus NP— constituye, de un lado, uno de los Problemas del Milenio, identificados por el Instituto Clay. Y de otra parte, sin ambages, se trata de la columna vertebral, por así decirlo, de todo el trabajo con fenómenos, sistemas y comportamientos complejos. Esto es, si cabe, es la columna vertebral de donde cuelgan músculos y órganos, vísceras y venas. Esto es, todo el cuerpo de estudio en complejidad. Haré aquí una presentación no técnica de P vs NP.
El problema de base consiste en identificar la clase de problemas que se tiene o con que se trabaja. Pues bien, desde el punto de vista al mismo tiempo computacional y lógico, todos los problemas se dividen en dos, así: de un lado, están los problemas llamados indecidibles; y de otra parte, los problema decidibles.
Que un problema sea o no “decidible” no quiere decir, en absoluto, que se lo pueda decir o no. Por el contrario, el tema se remonta a Hilbert. Un problema se dice que es indecidible si no sabemos —ni podemos saber— si o cuándo se detiene; esto es, por ejemplo, se resuelve. Más exactamente, los problemas indecidibles son todos aquellos en los que, supongamos, se puede tener tiempo ilimitado, espacio ilimitado, todos los recursos deseables: y ni aún así se los puede resolver. Ejemplos conspicuos de problemas indecidibles son la salud, el conocimiento, la naturaleza…
Un problema indecidible es aquel para el cual no existen algoritmos para resolverlo. En contraste, un problema decidible es aquel para el cual o bien existe un algoritmo para resolverlo, o ese algoritmo puede ser encontrado o desarrollado —en algún momento.
Pues bien, digamos que en el mundo empírico, mientras nos ocupamos con problemas indecidibles, hay que hacer cosas reales: asistir a clase, pagar un recibo, y demás. Los problemas decidibles son todos aquellos que se catalogan en dos grupos de la siguiente manera:
De un lado, están todos los problemas P, quiere decir aquellos problemas que se pueden abordar y resolver descomponiendo el problema en los términos que articulan o que componen al problema. En otras palabras, P son todos los problemas polinomiales. Más exactamente, por ejemplo, son los problemas que implican y admiten estrategias tales como histogramas, cronogramas, flujogramas y otros semejantes. En lógica, en ciencias de la computación y en matemáticas, un problema P es un problema fácil, que se puede resolver: y por eso mismo se llama, en propiedad, un problema irrelevante. Es irrelevante, matemática, lógica y computacionalmente todo aquello que puede ser resuelto.
De otra parte, están los problemas NP. Es posible decir que los problemas NP son todos aquellos problemas que ni pueden ser abordados ni resueltos descomponiendo el problema en los términos que lo componen. Así las cosas, NP significa no–polinomiales. Los problemas NP implican un tiempo no–polinomial. En lógica, en matemáticas y en computación un problema NP es un problema difícil y, por ello mismo, se dice que es relevante. Matemáticamente, lógica y computacionalmente se dice que un problema es relevante cuando no lo podemos resolver, pero creemos que debe ser posible una solución al mismo. Aun cuando no esté a la mano.
(Baste recordar que los polinomios consisten en operaciones algebraicas entre términos aritméticos).
Ahora bien, ¿podría pensarse que, en general, existen más problemas fáciles que difíciles? O bien, al contrario, que son más los problemas difíciles que los problemas fáciles, en ciencia como en la vida. O bien, desde otra perspectiva, ¿podría decirse que los problemas P están incluidos dentro de los problemas NP? ¿O al contrario?
Desde otra perspectiva, ¿puede decirse clara y distintamente que los problemas P son iguales a los NP (P = NP), o bien, al revés, que son manifiestamente diferentes (P ≠NP)?
La dilucidación de estos interrogantes da lugar a otras clasificaciones dentro de la clase de problemas P y NP, a saber: se trata de los problemas NP–duros (hard–NP problems), y de los problemas NP–completos.
En otras palabras, los problemas P vs NP constituyen el núcleo mitocondrial, si cabe la expresión, de todos los problemas relativos a la teoría de la complejidad computacional. Pero, ¿computar? Computar no es otra cosa que transformar una cosa en otra. En biología y en medicina esto se dice de otra forma: metabolizar. Al fin y al cabo, una de las funciones más fundamentales para que la vida sea posible consiste en metabolizar: cambiar una cosa (X) en otra (Y). Pues bien, la base de ello estriba en el reconocimiento de la clase de problemas con que nos enfrentamos.
Cabe decir que los problemas P vs NP tienen una grande variedad de campos en los que resultan altamente relevantes y pertinentes. Desde terrenos triviales, como el sudoku, hasta temas más sensibles computacional, lógica, matemática y militarmente hablando como la criptografía.
Los problemas P versus NP contienen, sin ningún lugar a dudas, el corazón de todos los problemas relativos a complejidad: ¿existen algoritmos para (casi) cualquier cosa? ¿Son necesarios, universales o no esos algoritmos? Algoritmos, en otras palabras, recetas, métodos, reglas, normas, procedimientos de acción y resolución de problemas. O bien, ¿existen en el mundo como en ciencia, fenómenos que son no–algorítmicos? ¿Es decir, que no obedecen, en absoluto, a normas, leyes, reglas, preceptos y mandamientos?
Nos encontramos en el centro de la complejidad, desde cualquier punto de vista, técnico o no.
Pues bien, resolver los interrogantes mencionados y otros parecidos y adyacentes constituye uno de los máximos retos en matemáticas. A ello, por ejemplo, invita a pensar el Instituto Clay.
Leave a Reply