Problema del vector más cercano (CVP) en un retículo

Definición del problema: 

Sea $\varLambda$ un retículo completo sobre $\mathbb{R}^n$ y sea $\vec{w} \in \mathbb{R}^n$.

Queremos encontrar un vector $\vec{z} \in \varLambda$ tal que:

$$\|\vec{w}-\vec{z}\| = mín\{\|\vec{w}-\vec{b}\|, \forall \vec{b} \in \varLambda\}$$

Es decir, dado un vector del espacio queremos encontrar el vector del retículo más cercano al primero. Esto se conoce como el Problema del Vector más Cercano (CVP, por las siglas en inglés "Closest Vector Problem").

 

Teniendo en cuenta que la región fundamental de un retículo es un n-paralelepípedo, es inmediato ver la relación con las entradas anteriores (1 y 2) en las que se plantea encontrar el vértice del n-paralelepípedo más cercano a un punto.

Resumiendo, para dimensiones altas el método exhaustivo consistente en calcular la distancia con todos los vértices del n-paralelepípedo tiene un coste computacional demasiado elevado. 

Por otra parte, el algoritmo de Babai solo ofrece garantías de obtener la solución correcta si la base es lo "suficientemente ortogonal". Pero a esto además le añadimos que con bases que tienen mucho defecto de ortogonalidad (muy "lejos" de ser ortogonales) resulta que el vector más cercano ni tan siquiera tiene porqué ser vértice del n-paralelepípedo que lo contiene.

Puede verse que hay un punto naranja (del retículo) más próximo a $Q$ que los vértices del n-paralelepípedo que lo contiene

Con todo lo anterior, podemos concluir lo siguiente sobre la resolución del problema del vector más próximo en un retículo: una persona que conozca una base "bastante próxima" a ser ortogonal podrá realizar los cálculos de manera relativamente sencilla, mientras que otra persona que conozca una base "suficientemente lejos" de ser ortogonal tendrá mucha más dificultad para resolverlo.