10 febrero 2007

SAT

Hace unos días escribí un comentario en el blog de XAngel sobre el problema de P=NP.

Hablé de SAT, el primer problema que se demostró que era NP-Completo. Este problema es muy sencillo: tienes una expresión lógica, por ejemplo

(A and B) or (not C and not B) or (not C and not A)

La pregunta a resolver es: ¿hay alguna combinación de valores True, False para A, B y C que hagan que esa expresión sea cierta? ¿cuál?

Una persona, pensando un poco podría encontrar la combinación pero para una máquina el cálculo tiene coste exponencial. Si en vez de 3 variables hubiera 100, un ser humano seguramente ni se atrevería a buscar la solución y un ordenador tardaría milenios en encontrar la solución.

Este es el problema SAT (Satisfiability).

No se conoce un algoritmo rápido para calcular la solución, sólo hay algoritmos exponenciales. Si se consiguiera encontrar uno, cambiaría radicalmente la informática que conocemos:


Is there an efficient solution to SAT? Is there some ingenious procedure that quickly determines whether any given proposition is satifiable or not? No one knows. And an awful lot hangs on the answer. An efficient solution to SAT would immediately imply efficient solutions to many, many other important problems involving packing, scheduling, routing, and circuit verification. This sounds fantastic, but there would also be worldwide chaos. Decrypting coded messages would also become an easy task (for most codes). Online financial transactions would be insecure and secret communications could be read by everyone. (MIT)



Se cree que no existe semejante algoritmo y que, de momento, la criptografía es hasta ciento punto, segura.