IA : Avances en Closest Vector Problem — problema del vector más cercano.

 Closest Vector Problem — problema del vector más cercano.

Aquí la idea central es:

La IA habría demostrado una nueva dureza de aproximación para CVP: no solo es difícil encontrar el vector más cercano exacto en un retículo, sino que sigue siendo NP-difícil aproximarlo dentro de un factor polinómico ${𝑛}^{1\mathrm{/}400}$.

No es un resultado sobre “encontrar mejores algoritmos”, sino sobre demostrar que cierta aproximación no puede hacerse eficientemente salvo que P = NP.

1. Qué es el Closest Vector Problem

Un retículo o lattice es el conjunto de todos los puntos que puedes generar combinando vectores base con coeficientes enteros.

Si tienes una matriz base $𝐵$, el retículo es:

$$𝐿(𝐵)=𝐵{\mathbb{𝑍}}^{𝑛}$$

El Closest Vector Problem, CVP, pregunta:

Dado un punto objetivo $𝑡$, ¿cuál es el punto del retículo más cercano a $𝑡$?

Formalmente, se busca:

$${\mathrm{dist}}_2(𝑡,𝐿(𝐵))=\underset{𝑧\in {\mathbb{𝑍}}^{𝑛}}{\min }\mathrm{\parallel }𝑡-𝐵𝑧{\mathrm{\parallel }}_2$$

El paper de OpenAI formula la versión aproximada como un problema de promesa: distinguir si la distancia es como mucho $𝑟$, o si es mayor que $𝛾(𝑛)𝑟$, donde $𝛾(𝑛)$ es el factor de aproximación.

2. Qué ha demostrado exactamente la IA

El resultado principal dice que existe una reducción determinista en tiempo polinómico desde 3SAT a CVP euclídeo tal que:

$$𝜑\text{ satisfacible}\Rightarrow {\mathrm{dist}}_2(𝑡,𝐿(𝐵))\le 𝑟$$$$𝜑\text{ no satisfacible}\Rightarrow {\mathrm{dist}}_2(𝑡,𝐿(𝐵))>{𝑛}^{1\mathrm{/}400}𝑟$$

Por tanto, aproximar CVP euclídeo dentro de un factor ${𝑛}^{1\mathrm{/}400}$ es NP-difícil. El manuscrito subraya que la reducción es directa desde 3SAT y no usa PCP, aleatoriedad ni la Projection Games Conjecture.

Esta precisión importa mucho. No es “CVP es difícil”, que ya se sabía en varias formas. Es:

CVP sigue siendo difícil incluso si aceptas una aproximación polinómica fija.

El exponente $1\mathrm{/}400$ parece pequeño, pero matemáticamente es importante porque es un exponente constante positivo.

3. Por qué CVP importa

CVP es uno de los problemas centrales de la geometría de números y aparece conectado con optimización entera, teoría computacional de números y criptografía. El propio paper recuerda que los problemas de retículos son relevantes para criptografía de clave pública y postcuántica, aunque aclara que los sistemas criptográficos prácticos se apoyan normalmente en supuestos estructurados o de caso medio, no directamente en la NP-dureza peor-caso de CVP.

Es decir, el resultado no significa automáticamente “la criptografía postcuántica es segura” ni “está rota”. Significa algo más fundamental:

ciertos problemas geométricos en retículos tienen una barrera computacional profunda incluso para aproximaciones bastante gruesas.

4. La ruta de la prueba

La reducción tiene dos pasos:

$$3𝑆𝐴𝑇⟶\text{Binary Nearest Codeword}⟶\text{Euclidean CVP}$$

El segundo paso, de códigos binarios a retículos, es estándar. La contribución nueva está en el primer paso: construir desde una fórmula 3SAT un problema binario de “palabra más cercana” con una brecha suficientemente fuerte.

En lenguaje simple:

1. Se parte de una fórmula lógica 3SAT.
2. Se codifican sus asignaciones posibles como objetos algebraicos.
3. Se construye un sistema binario $𝐻𝑥=𝑏$.
4. Si la fórmula es satisfacible, existe una solución de bajo peso.
5. Si no es satisfacible, cualquier solución tiene peso mucho mayor.
6. Ese salto de peso se convierte en una distancia en un retículo.

5. El problema intermedio: nearest codeword

Un código binario lineal es un subespacio:

$$𝐶\subseteq {\mathbb{𝐹}}_2^{𝑛}$$

El problema de la palabra más cercana pregunta:

Dada una palabra recibida $𝑢$, ¿cuál es la palabra del código $𝐶$ más cercana a $𝑢$ en distancia de Hamming?

La distancia de Hamming cuenta cuántas coordenadas cambian. El paper también usa la versión equivalente de syndrome decoding: dado $𝐻$, $𝑏$ y un radio, buscar una palabra de bajo peso que satisfaga $𝐻𝑥=𝑏$.

La IA habría conseguido una brecha de aproximación ${𝑛}^{1\mathrm{/}200}$ para nearest codeword y syndrome decoding. Al pasar de distancia de Hamming a distancia euclídea, aparece una raíz cuadrada, y por eso el exponente se convierte en ${𝑛}^{1\mathrm{/}400}$ para CVP euclídeo.

6. La idea clave: codificar asignaciones con Reed–Solomon

Aquí aparece la parte bonita.

Una asignación booleana de una fórmula 3SAT se codifica como un polinomio. Se elige un cuerpo finito de característica dos:

$$𝐾={\mathbb{𝐹}}_{2^{𝑒}}$$

y puntos especiales ${𝑎}_1,\dots ,{𝑎}_{𝑚}$. Una asignación $𝜎\in \{0,1{\}}^{𝑚}$ se representa mediante el único polinomio ${𝑄}_{𝜎}$ que cumple:

$${𝑄}_{𝜎}({𝑎}_{𝑖})={𝜎}_{𝑖}$$

Esto es el punto de vista Reed–Solomon: una palabra/código se ve como la evaluación de un polinomio en muchos puntos. El walkthrough explica que esta representación permite transformar una asignación booleana en una tabla de valores algebraicos.

En lenguaje intuitivo:

una solución lógica se convierte en una curva algebraica de baja complejidad.

7. Tablas globales y tablas de cláusulas

La construcción introduce variables binarias del tipo:

$${𝑥}_{𝜏,𝑝,𝑤}$$

donde:

• $𝜏$ indica el tipo de tabla;
• $𝑝$ es un punto de evaluación;
• $𝑤$ es un posible valor del polinomio.

Hay una tabla global, que representa la asignación completa, y tablas locales para cada cláusula y cada posible asignación local que satisface esa cláusula. Si la fórmula es satisfacible, la tabla global y las tablas de cláusulas seleccionadas coinciden en los valores del mismo polinomio ${𝑄}_{𝜎}$.

La condición clave es que todo esto se transforma en un sistema binario lineal:

$$𝐻𝑥=𝑏$$

Aunque aparecen expresiones que parecen momentos o potencias, las incógnitas son solo los indicadores binarios ${𝑥}_{𝜏,𝑝,𝑤}$. Las potencias de $𝑤$ son coeficientes ya conocidos dentro del cuerpo finito. Por eso las condiciones aparentemente no lineales siguen siendo lineales.

Este es uno de los golpes conceptuales:

la IA convierte consistencia lógica global en restricciones lineales sobre histogramas algebraicos.

8. El obstáculo: evitar cancelaciones falsas

El gran problema era que trabajar en característica dos permite cancelaciones. Una solución de bajo peso podría intentar “hacer trampas”: no representar una asignación real, sino una mezcla algebraica que satisface las ecuaciones por paridad.

El walkthrough dice que el obstáculo común era precisamente la cancelación: había que forzar que cualquier objeto global corto codificara al menos una asignación satisfactoria consistente.

Es decir, no bastaba con construir ecuaciones. Había que impedir que una pseudo-solución ligera pareciera válida sin venir de una asignación real.

9. La innovación: reconstrucción por momentos de Hankel

Supongamos que existe una solución binaria de bajo peso. Para cada tipo de tabla $𝜏$, se mira el conjunto de valores seleccionados:

$${𝑆}_{𝜏}(𝑝)=\{𝑤:{𝑥}_{𝜏,𝑝,𝑤}=1\}$$

La prueba usa momentos de esos conjuntos y matrices de Hankel. Si los momentos son compatibles y el peso es pequeño, se puede reconstruir un polinomio separable cuyos raíces representan los posibles valores seleccionados. La clave técnica es que el determinante de Hankel se convierte en un cuadrado de Vandermonde cuando hay valores distintos, y esto permite reconstruir raíces incluso en característica dos.

Traducción sencilla:

si una solución ligera intenta esconderse como mezcla de valores, los momentos permiten recuperar las raíces algebraicas que la componen.

Es como reconstruir los ingredientes de una mezcla a partir de suficientes medidas agregadas.

10. Shifted moments: forzar una asignación común

Reconstruir raíces no basta. Hay que demostrar que existe una misma raíz global compatible con todas las cláusulas.

Aquí entran los momentos desplazados. Para una cláusula $𝐶$, una asignación local satisfactoria $𝛽$ y una variable $𝑖$ de esa cláusula, se consideran expresiones del tipo:

$$\frac{𝑤-{𝛽}_{𝑖}}{𝑝-{𝑎}_{𝑖}}$$

La razón es que, si $𝑤={𝑄}_{𝜎}(𝑝)$ y ${𝑄}_{𝜎}({𝑎}_{𝑖})={𝛽}_{𝑖}$, entonces:

$$\frac{{𝑄}_{𝜎}(𝑋)-{𝛽}_{𝑖}}{𝑋-{𝑎}_{𝑖}}$$

sigue siendo un polinomio. Esa pequeña mejora de grado permite detectar si la asignación local $𝛽$ es coherente con la asignación global.

Después se usan valoraciones algebraicas. Si dos cláusulas intentan asignar valores distintos a la misma variable, las valoraciones producirían una contradicción ultramétrica. El walkthrough resume la síntesis decisiva como reconstrucción separable, emparejamiento por paridad y compatibilidad por valoraciones.

En lenguaje llano:

la IA no solo demuestra que hay raíces; demuestra que las raíces obligan a elegir una asignación booleana única y coherente para todas las cláusulas.

11. De sistema binario a retículo: el “parity lift”

Una vez construido el sistema binario $𝐻𝑥=𝑏$, se pasa a un retículo entero mediante reducción módulo 2.

Se define el código:

$$𝐶={\ker }_{{\mathbb{𝐹}}_2}𝐻$$

y el retículo:

$${\mathrm{\Lambda }}_{𝐻}=\{𝑧\in {\mathbb{𝑍}}^{𝑀}:𝐻(𝑧<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>2)=0\}$$

La instancia de syndrome decoding se transforma en buscar el punto de este retículo más cercano a un vector objetivo. El paper da la identidad exacta:

$$\underset{𝑧\in {\mathrm{\Lambda }}_{𝐻}}{\min }\mathrm{\parallel }𝑢-𝑧{\mathrm{\parallel }}_{𝑝}^{𝑝}=\min \{\mathrm{wt}(𝑥):𝐻𝑥=𝑏\}$$

para $𝑝\ge 1$.

Esto es crucial: la distancia al retículo reproduce exactamente el peso de una solución binaria.

Para $𝑝=2$, la norma euclídea introduce raíz cuadrada. Por eso una brecha ${𝑀}^{1\mathrm{/}200}$ en peso binario se convierte en una brecha ${𝑀}^{1\mathrm{/}400}$ en distancia euclídea.

12. Qué NO significa

No significa que todos los algoritmos de retículos sean inútiles.

No significa que todos los problemas usados en criptografía postcuántica estén resueltos o sean equivalentes a CVP peor-caso.

No significa que el exponente $1\mathrm{/}400$ sea óptimo.

El propio paper distingue la relevancia de los problemas de retículos para criptografía de los supuestos prácticos usados en criptosistemas reales, que suelen ser estructurados o de caso medio.

Lo que sí significa es:

se obtiene una barrera de NP-dureza directa y polinómica para aproximar CVP euclídeo, con una reducción explícita desde 3SAT.

13. Qué significa que lo haya hecho la IA

Según OpenAI, este resultado forma parte de los diez avances generados por un modelo interno y acompañados por manuscritos y formalizaciones. El repositorio oficial lista GapCVP.lean como certificado Lean asociado al resultado sobre polynomial-factor hardness para CVP, decoding y problemas de retículos.

Lo interesante no es solo que el modelo haya producido una prueba. Es el tipo de arquitectura que descubre:

lógica booleana → códigos Reed–Solomon → histogramas binarios → momentos → reconstrucción algebraica → sistema lineal → retículo entero.

Esa cadena es el avance.

14. Lectura RMS / pensamiento complejo

En clave RMS:

Recursos: fórmulas 3SAT, cuerpos finitos de característica dos, polinomios Reed–Solomon, tablas binarias, momentos, códigos lineales, retículos enteros, normas ${\mathrm{\ell }}_{𝑝}$.

Mecanismos: interpolación, restricciones de baja dimensión, paridad, reconstrucción de raíces por Hankel/Vandermonde, compatibilidad por valoraciones, conversión módulo 2 a retículo, pérdida de raíz cuadrada en norma euclídea.

Sistema: una arquitectura que transforma satisfacción lógica en cercanía geométrica.

La enseñanza sistémica es muy clara:

un problema geométrico —encontrar el punto más cercano de un retículo— se vuelve difícil porque dentro de la geometría se ha codificado una estructura lógica global.

Síntesis final

La IA habría demostrado que aproximar el Closest Vector Problem euclídeo dentro de un factor ${𝑛}^{1\mathrm{/}400}$ es NP-difícil. La prueba no usa PCP ni conjeturas externas: construye una reducción directa desde 3SAT. Primero transforma asignaciones booleanas en polinomios Reed–Solomon sobre característica dos; después codifica cláusulas mediante tablas binarias y momentos; luego demuestra que cualquier solución ligera permite reconstruir una asignación global satisfactoria; finalmente levanta el sistema binario a un retículo entero mediante paridad. En clave RMS, es otro caso de cambio de representación: de lógica a códigos, de códigos a álgebra, de álgebra a geometría de reticulos