Creo que es un algoritmo de mejor esfuerzo de tiempo polinómico para resolver un problema NP-completo. LLL es muy muy útil para romper los sistemas criptográficos de mochila.
El problema de red que resuelve LLL es el siguiente. Dado un conjunto básico de vectores (cuyas entradas son enteros), encuentre una combinación lineal de estos vectores que tenga la norma más pequeña. Los pesos en los vectores en la combinación lineal deben ser enteros.
Alternativamente, encuentre el vector en la red más cercana a otro vector.
Digamos que tenemos los vectores x ^ = (1,4) e y ^ = (3, -6)
- ¿Qué es el algoritmo de Viterbi y cómo se aplica a las comunicaciones inalámbricas CDMA / 3G / 4G?
- Dado un gráfico, ¿existe un enfoque bien conocido para determinar si el gráfico es bipartito? Si es así, ¿hay alguna forma de particionar el gráfico? Cuales son las formas?
- ¿Existe un algoritmo óptimo para jugar Bejeweled?
- ¿Por qué las computadoras pueden completar algunas tareas excepcionalmente bien y otras terriblemente?
- ¿Cuál es el algoritmo matemático para el reflejo del equilibrio humano?
Consideramos todas las combinaciones lineales a * x ^ + b * y ^ donde a y b son enteros. El conjunto de todas estas combinaciones lineales se denomina “la red” generada por el conjunto base x ^ e y ^.
El problema de determinar si un vector está en una red entera dada, creo que es trivial (parece trivial, pero no estoy seguro). Sin embargo, por alguna razón, el problema de la red es NP-completo. Puede ver esto al observar que el problema de la red entera se reduce al problema de la mochila (de alguna manera, olvidé por qué).
El problema de la mochila es el siguiente; dado un conjunto de enteros, determine si un subconjunto se suma a un número determinado.
Parece trivial, pero hay 2 ^ n subconjuntos de un conjunto de elementos n y el problema es formalmente NP completo, aunque existen algoritmos extremadamente poderosos para resolverlo.
El problema de la mochila es un “parece fácil, es fácil, pero formalmente es un problema de NP completo”. Muchas personas han intentado usar redes enteras y problemas de mochila como la base de los sistemas criptográficos, pero son triviales de romper.
NP-complete no significa difícil. Podemos resolver mil millones de problemas variables “difíciles” de 3-SAT en menos de una hora en una sola CPU, utilizando los algoritmos correctos.
El algoritmo LLL garantiza con alta probabilidad que encuentre un vector corto en tiempo polinómico. Sin embargo, el vector no siempre es el vector más corto en la red, pero a menudo se acerca y muchas veces encuentra la solución más corta o una solución lo suficientemente buena.