Intento revisar y comprobar dónde me equivoco

Como si no tuviera bastante para sustos, ahora voy y descubro que mis mecanismos (bastante consolidados)..., determinar si una fórmula booleana se puede satisfacer resulta que se puede hacer incluso más rápido que el algoritmo de Floyd.



Voy a hacer una parada en mitad del camino. La verdad es que estoy un tanto absorto: no gano para sustos. Por un lado lo veo lógico, pero por el otro, ¿qué pasa? ¿Acaso voy a ser el único que siga avanzando en el mundo de la lógica y la computación? Obviamente...

El asunto es que ayer descubrí una optimización sobre mi tecnología que daba una nueva vuelta de tuerca al asunto. Me recordó a una vieja conversación con un amigo..., y con más de uno. Al final pasa lo que pasa:

- ¡Bah! La informática no es para tanto. Piensa que lo que se estudia se puede imaginar y esos teoremas son todos intuitivos.

- ¿Estás seguro de ello? - le dije yo a mi compañero de autobús - ¿Has pensado en la posibilidad de que pudiera tener una cuestión para la cual podrías dar una respuesta intuitiva errónea?

- Pues adelante, tenemos tiempo antes de llegar a Cartagena.

- Allá va. Imagina que este autobús adopta varios caminos para llegar a su destino, puntos por los que no podrá pasar dos veces a la hora de dejar a sus viajeros. A la hora de elegir una dirección ésta puede formar parte del camino más corto para llegar a su objetivo, el camino más largo o ninguno de los dos..., por ejemplo.

- Sí, pero aún quedaría una cuarta opción.

- Efectivamente, podría formar parte la decisión de ir por un cierto camino tanto del camino más corto como del camino más largo. La cuestión es harta sencilla: a la hora de etiquetar si el camino escogido forma parte o no del camino más corto y si forma parte o no del camino más largo, ¿cuál de las dos etiquetas es más fácil de decidir poner?

Mi compañero de autobús se quedó pensando y, al final, acabó respondiendo lo mismo que suele responder una cierta mayoría cuando soy yo el que expone el problema en cuestión:

- Pues es más fácil de decidir si este camino forma parte del camino más largo.

- ¿Estás diciendo que resulta más fácil saber cuál es el camino más largo antes de cuál es el camino más corto a la hora de crearse un trayecto?

- Sí - dijo después de quedarse un rato pensando.

- Pues no - respondí yo - si realmente tienes un mecanismo que permite hallar el camino más largo antes que el más corto existe una recompensa de un millón de euros porque, de hecho, se considera que incluso es posible que no se pueda resolver de manera sencilla. Vamos, que si el problema supusiera enormes costes determinar el camino más corto, es posible que el camino más largo jamás pudiera ser determinado debido a los enormes costos de cómputo que representa...

...

Así fue la conversación. El hombre tenía estudios superiores casi terminados en bioquímica. Pero no sabía lo que los informáticos nos suponíamos, y todos sobreentendíamos. Era un hecho: no existía un algoritmo que permitiera encontrar el camino más largo antes que el más corto, de hecho, suena infantil y absurdo cuando estudias a Dijkstra y lo que significa el principio de optimabilidad.

Sin ir más lejos, muchos habríamos estudiado la cercanía entre los problemas de la clase NP y los de la clase P a través del principio de optimabilidad, para establecer que esos problemas que eran fáciles de validar debían estar, en el mejor de los casos, un par de bucles por encima del algoritmo de Floyd (el que calcula el camino más corto en grafos ponderados haciendo uso el principio de optimabilidad de Dijkstra).

Pues bien. Tortazo en la cara. El bioquímico tenía razón. En cuanto lo vea le pido disculpas. El algoritmo de Floyd es O(n^3), mientras que los problemas vinculados directamente con la clase NP-co he comprobado con una nueva técnica que tienen una complejidad O(n^2log n). Le adelanta por una cabeza.

En cierta manera, considerando que el algoritmo de Dijkstra es O(n^2) se puede comprender. Es como decir que están peor condicionados los problemas que no son fáciles de verificar a la hora de ponerles ponderación, a la hora de endurecerlos un poco. Esa sería la justificación que le podría dar a posteriori.

En cualquier caso, es increible el juego que me está dando el álgebra abstracta. No sé si me pasará como a Dijkstra y un hijodeputa (Floyd) se me adelantará, publicará mi algoritmo antes que yo y se valdrá de mi tecnología para justificar la O grande que he expuesto - y lo digo porque no soy ni mucho menos experto en noetherianos ni en ideales. Y ése es mi pesar: cualquier día aparece un americano de alguna hermandad importante y se le atribuye todos mis méritos sólo por ser capaz de hacer algo un pelín más formal que yo..., que aproveche lo que no sabe de mí, para introducir su literatura algebraica sobre los aspectos que aún no tengo pulido.

Claro, si dispusiera de tiempo, aliados..., podría tomármelo con calma. Pero, por otro lado, igual que el principio de optimabilidad y los grafos expandidos no se lo podrá arrebatar a nadie a Dijkstra, a mí nadie me podrá arrebatar mis funciones de alternancia y el método de afilamiento.

Luego está la valoración más importante: el sujeto que me robe será famoso por un tiempo..., pero el Olvido le llegará a él antes que a mí. Es decir, de existir tal sujeto, sé que no le funcionará. Juego con ventaja, pues la tecnología es mía y, quien quiera aprovecharla intentando pirateármela (no mencionándome según corresponda), le saldrá el tiro por la culata - porque mis estructuras son demasiado exclusivas y originales.

Así que..., seguiré redactando el documento. Aunque hay una única demostración que me obliga a no poder usar según qué términos que lo haría todo más..., perfecto. Son cosas de la literatura matemática cuando se trata de álgebra. Por lo que, ¿es importante? ¿No lo es?

Y es que todo huele mal cuando observamos que el principal problema que tengo no es el de hacer nuevos descubrimientos, o de hacer cosas innovadoras..., el problema es que todo eso lo estoy haciendo casi en exclusividad, se puede corroborar fácilmente en cualquier computador de casa, si se testeara en un superordenador los resultados serían apoteósicos y..., nada, no consigo que me hagan caso.

Obviamente algo está fallando. Sobretodo cuando soy yo: uno de los mayores expertos en hacer que me hagan caso. Es decir, todo huele a chamusquina, pero a una chamusquina de aupa.