Las clases del profesor Polymeris pueden ser de tres típos: absolutamente marcianas, si es que no entraste con las pilas puestas y con los ojos bien abiertos, marcianas, si entraste con un ánimo como diciendo ahora si que no me duermo, pero caes rendido ante la cruda matemática o un desafío si fuiste uno de los elegidos y entendiste algo de lo que el profe habló en la clase. Hoy (hace unos días en realidad este post lo rescate del baúl de los recuerdos, 21 de Octubre de 2005) estuve en el grupo de los últimos. El tema de la clase era ver si para un conjunto de cláusulas de Horn se podía determinar en un tiempo polinomialmente acotable (eficiente) si el conjunto era -o no- satisfacible, es decir, que existe al menos una valuación de verdad que hace verdadero a todos los elementos del conjunto. Los detalles matemáticos no importan mucho, lo que me interesa compartir es el sentimiento del tema. En el caso de las cláusulas de Horn (cdH), si existe un algoritmo eficiente que resuelve este problema, sin embargo, esas cláusulas o tipos de formulas lógicas son una reducción de lo que podemos escribir con la lógica de primer orden completa.
Vamos por parte. Con las cdH, podemos escribir dos tipos de expresiones lógicas:

a) (x1 y x2 y… y xn) -> xm, que equivale a decir que de una serie de hechos (xi), se deduce o implican otro.
b) (nox1 y nox2 y … y noxn), lo que equivale a decir que una serie de hechos no están relacionados o nunca ocurren juntos.

Los defensores de las cdH sostenían que utilizando estas dos construcciones lógicas se podía modelar todo el conocimiento, sin embargo, estas dos estructuras dejan de lado expresiones del tipo:

c) x1 y x2 y x3 y x4 -> (x5 y x6) o (x7 y x8) que equivalen a decir algo asi como que un conjunto de hechos producen alguno(s) de varios posibles. A primera vista estas últimas cláusulas sólo aportan conocimientos vagos, sin embargo, varias de ellas pueden derivar en un conocimiento concreto como el expresado en a) o en b)

Pero, cuando incorporamos ese tipo de cláusulas (c), ya no existen algoritmos como el que buscamos*. La clase derivó finalmente en que al parecer, estamos condenados a limitar nuestra expresividad para poder obtener resultados computacionalmente eficientes, sin embargo, en la práctica, no podemos limitarnos y debemos buscar nuevas alternativas para intentar solucionar estos problemas (heurísticas, algoritmos genéticos, redes neuronales, etc..). Pareciera que hay algo allá afuera, que nos esta topando el paso.

*Si alguien llegara a encontrar este algoritmo, demostraría que P=NP (problemas polinomialmente acotables y problemas polinomialmente acotables en una maquina no determinista), una de las interrogantes más importántes en la matemática actual. Aparte del reconocimiento universal, practicamente todos los problemas de la computación se superarían.

En la imágen, Stephen Cook, ganador del premio Turing por descubrir la clase de problemas NP-Completos