sábado, noviembre 04, 2006

Momento de ego

Ayer tuvimos una junta de más de dos horas mi asesor, Meng, y yo intentando decidir qué tanto tenemos para un artículo en la complejidad de encontrar explicaciones mínimas para ciertos sucesos, usando una lógica muy básica.
El punto es que sabemos que el problema general, encontrar todas las explicaciones, es exponencial; encontrar una de cierto tamaño es NP-completo, y encontrar una cualquiera es polinomial. El problema es que el algoritmo polinomial (que es trivial) es de hecho muy ineficiente, pues requiere revisar todos los axiomas y, como queremos aplicarlo a un sistema con unos cuantos millones de ellos, no resulta práctico.
Meng tuvo entonces una idea, que básicamente consiste en modificar el algoritmo que encuentra todas las explicaciones, de tal forma que encuentre sólo una. Este algoritmo modificado también corre en tiempo polinomial y es claramente mucho más eficiente que el otro, pero no hemos podido probar que el resultado es realmente una explicación mínima.
Resulta ser uno de esos problemas en los que no tienes ni idea; cada vez que lo pienso, cambio mi parecer entre que sí es cierto que encuentra una mínima y que no. Todo me parece indicar que no, pero cualquier forma de construir un contraejemplo requiere pasos que no realiza el algoritmo, o axiomas en una forma que no está permitida. Tras mucho tiempo de discusión, decidimos que era mejor tratarlo después, pues seguro hay algo que no estamos viendo. Y ahí es donde surgió el momento de ego que quiero narrar.
Cuando nos despedíamos, Baader dijo: "entonces, ¿todos saben lo que tienen que hacer? "Meng y yo nos miramos con cara de despistados y luego dijo "Rafael, demuestra lo que hace falta, Meng implementa y yo espero". Sé que fue una broma, pero me dio gusto que confiara en mí para esta demostración a la que todavía no veo luz; en todo caso, espero poder pronto decir que está resuelto.

2 comentarios:

juan antonio dijo...

jaja.. muy bueno (y), así que suerte con la demostración!

Rafael Peñaloza dijo...

Muchas gracias, Juan. Espero que la demostración no se demore en llegar.