IA-Avances: Complejidad de circuitos aritméticos (Arithmetic circuit complexity)

Complejidad de circuitos aritméticos.

Aquí el resultado es menos “visual” que sphere packing o códigos, pero es quizá uno de los más importantes para teoría de la computación:

La IA habría demostrado nuevas cotas inferiores para calcular el permanente usando circuitos aritméticos y fórmulas aritméticas.

En lenguaje simple: ha probado que cierto polinomio central —el permanente— necesita inevitablemente una cantidad mínima de operaciones algebraicas. No basta con que alguien no haya encontrado un algoritmo mejor; se demuestra que, dentro de ciertos modelos, no puede existir un cálculo demasiado pequeño.

1. Qué es el permanente

El permanente se parece mucho al determinante. Para una matriz $n\times n$,

$$\operatorname{per}_n(X)=\sum_{\sigma\in S_n}\prod_{i=1}^{n}x_{i,\sigma(i)}$$

La suma recorre todas las permutaciones. Cada término elige una entrada de cada fila y de cada columna. El manuscrito lo interpreta también como elegir un matching perfecto en un grafo bipartito completo. La diferencia con el determinante es que el determinante pone signos $+$ y $-$, mientras que el permanente suma todos los términos con signo positivo. Esa diferencia parece pequeña, pero computacionalmente es enorme: el determinante tiene circuitos algebraicos de tamaño polinómico, mientras que el permanente es completo para la clase algebraica VNP de Valiant

La pregunta profunda es:

¿Puede el permanente calcularse con circuitos aritméticos pequeños, o necesita inevitablemente muchos recursos?

Esto es uno de los grandes núcleos de la complejidad algebraica, una versión algebraica del tipo de preguntas P vs NP.

2. Qué es un circuito aritmético

Un circuito aritmético es un grafo de cálculo con entradas, constantes y operaciones:

$$+,-,\times$$

La clave es que un circuito puede reutilizar resultados intermedios. Si una parte del cálculo sirve varias veces, se calcula una vez y se comparte. El paper define estos circuitos como grafos acíclicos dirigidos, con puertas internas de suma, resta o multiplicación, y mide el tamaño por el número de puertas aritméticas.

Una fórmula aritmética es más restrictiva: es un árbol. No hay reutilización. Si necesitas el mismo subcálculo dos veces, lo tienes que recomputar dos veces. El propio paper distingue ambos modelos y permite también fórmulas con división válida, siempre que los denominadores no sean racionalmente cero.

La diferencia sistémica es clara:

Modelo	Qué permite
Circuito	Reutilizar subcálculos
Fórmula	No reutiliza; todo se recompone como árbol
Fórmula con división	Permite cocientes intermedios, pero el resultado final debe ser el polinomio correcto

3. Qué ha demostrado la IA

Según el manuscrito de OpenAI, para el permanente hay dos resultados principales.

Primero: circuitos aritméticos sin división.
Se demuestra que todo circuito sin división que calcule exactamente el permanente necesita:

$$\mathrm{\Omega }({𝑛}^2\log \log 𝑛)$$

puertas aritméticas. Más concretamente, para $𝑛\ge 2^{16}$, el paper da una cota explícita:

$$𝐶({\mathrm{per}}_{𝑛})\ge \frac{{𝑛}^2}{144}({\log }_2{\log }_2𝑛-3)$$

Esto es importante porque supera la cota elemental $\mathrm{\Omega }({𝑛}^2)$, que simplemente dice: el permanente depende de las ${𝑛}^2$ variables de la matriz. El avance es que el coste por variable crece lentamente, pero crece.

Segundo: fórmulas aritméticas.
Para fórmulas sin división, obtiene:

$${𝐿}_{\mathrm{v}\mathrm{a}\mathrm{r}}(\mathrm{\Phi })\ge \frac{{𝑛}^4}{128{\log }_2𝑛}$$

y para el número de puertas internas:

$$𝐺(\mathrm{\Phi })\ge \frac{{𝑛}^4}{256{\log }_2𝑛}$$

Incluso si se permiten divisiones válidas, la cota sigue siendo del mismo orden:

$$\mathrm{\Omega }\left(\frac{{𝑛}^4}{\log 𝑛}\right)$$

con constantes algo peores.

La página del repositorio de formalizaciones resume este resultado como nuevas cotas inferiores para calcular el permanente con circuitos y fórmulas, incluyendo la cota de fórmulas ${𝑛}^4\mathrm{/}\log 𝑛$, y asocia el certificado Lean al archivo Permanent.lean.

4. Qué NO significa

Conviene no exagerarlo.

Esto no resuelve VP vs VNP.
No prueba todavía que el permanente requiera circuitos superpolinómicos.
No demuestra que sea imposible todo algoritmo algebraico eficiente.

Pero sí mejora el suelo conocido en modelos muy generales:

para circuitos sin división, el permanente no solo necesita mirar ${𝑛}^2$ variables; necesita más que eso: $\mathrm{\Omega }({𝑛}^2\log \log 𝑛)$.

Y para fórmulas, el resultado es mucho más fuerte:

sin reutilización de subcálculos, el coste se dispara hasta casi ${𝑛}^4$, salvo un factor logarítmico.

5. La idea de la prueba para circuitos: mirar el gradiente

La primera vía de la IA fue no contar monomios directamente. Eso suele fallar porque los circuitos pueden compartir, cancelar y reorganizar términos.

El giro fue mirar la geometría del polinomio.

Para un polinomio $𝑃$, se estudia su gradiente:

$$\mathrm{\nabla }𝑃=(\frac{\mathrm{\partial }𝑃}{\mathrm{\partial }{𝑥}_1},\dots ,\frac{\mathrm{\partial }𝑃}{\mathrm{\partial }{𝑥}_{𝑚}})$$

y su lugar crítico:

$$\mathrm{Crit}(𝑃)=\{𝑥:\mathrm{\nabla }𝑃(𝑥)=0\}$$

La idea es:

si el lugar crítico de un polinomio tiene codimensión grande, entonces calcular ese polinomio exige muchos productos.

El walkthrough explica que, si $𝑃$ es homogéneo de grado $𝑑$, tiene $𝑚$ variables y el lugar crítico tiene codimensión al menos $𝑘$, se puede restringir el gradiente a un subespacio de dimensión $𝑘$ y construir un mapa cuadrado:

$$𝐹:{\mathbb{𝐶}}^{𝑘}\to {\mathbb{𝐶}}^{𝑘}$$

que solo se anula en el origen. Entonces una fibra genérica tiene $(𝑑-1{)}^{𝑘}$ puntos. Si un circuito con $𝑞$ multiplicaciones calcula ese mapa, una cota de Bézout fuerza:

$$(𝑑-1{)}^{𝑘}\le 2^{𝑞}$$

y, usando diferenciación eficiente tipo Baur–Strassen, se obtiene una cota inferior para el circuito original:

$$𝐿\ge \frac{𝑘{\log }_2(𝑑-1)}{3}$$

En lenguaje simple:

un circuito pequeño no puede generar una geometría crítica demasiado complicada.

6. Por qué había que usar algo específico del permanente

Uno podría pensar: “apliquemos eso directamente al permanente entero”. Pero no era tan fácil.

El walkthrough dice que la esperanza inicial era que el mapa gradiente del permanente tuviera un grado genérico enorme. Sin embargo, aparecen componentes críticas grandes, por ejemplo si hay dos filas cero. Eso impide usar una cuenta ingenua de Bézout. También fallan enfoques por volúmenes de Newton, tropicalización o tratar los coeficientes como independientes, porque los matchings del permanente están muy correlacionados.

La IA encontró entonces una estrategia más fina:

construir una especialización afín del permanente que conserve muchas variables pero tenga un lugar crítico de codimensión grande.

La pieza básica es un polinomio de sumas de matchings rectangulares. Después, mediante inclusión-exclusión por columnas, se controla el lugar crítico. La prueba necesita mantener $𝑚=\mathrm{\Theta }({𝑛}^2)$ variables y conseguir codimensión crítica $\mathrm{\Theta }(𝑚)$.

7. El truco de las raíces de la unidad

El problema siguiente era: no basta con tener muchos bloques buenos por separado. Hay que meterlos dentro de un solo permanente.

Si multiplicas bloques, el lugar crítico se estropea: para un producto ${𝑓}_1{𝑓}_2$, basta con que ambos factores se anulen para que el gradiente se anule. Eso genera demasiadas singularidades.

La IA usa una suma de bloques en variables disjuntas, porque ahí las codimensiones críticas sí se suman. Pero esa suma debía realizarse como una única especialización del permanente.

Ahí aparece el truco de cancelación por raíces de la unidad. El walkthrough muestra una matriz ejemplo donde los términos mixtos se cancelan y solo sobreviven los permanentes internos de bloque. En la construcción general, se usan columnas constantes y raíces $𝑑$-ésimas de la unidad para cancelar los términos cruzados y conservar los bloques deseados dentro de un único permanente.

Esta es la idea sistémica:

no se calcula cada bloque por separado; se diseña una arquitectura donde el permanente global contiene muchos bloques útiles y cancela automáticamente las interferencias.

8. Resultado para circuitos: el mecanismo completo

La prueba de circuitos combina cuatro piezas:

1. Geometría crítica: un polinomio con lugar crítico de alta codimensión exige muchos productos.
2. Diferenciación eficiente: Baur–Strassen permite calcular todas las derivadas con sobrecoste constante.
3. Especialización del permanente: se construyen polinomios derivados del permanente con alta codimensión crítica.
4. Cancelación por raíces de la unidad: permite sumar muchos bloques dentro de una sola instancia del permanente.

El walkthrough resume que la fuerza del resultado viene de la interacción entre esos ingredientes, no de una sola técnica aislada.

En clave RMS:

Recursos: permanente, derivadas, matchings, raíces de la unidad, especializaciones afines.
Mecanismos: lugar crítico, codimensión, Bézout, diferenciación, cancelación.
Sistema: una prueba que convierte complejidad computacional en geometría algebraica.

9. La prueba para fórmulas: otro mecanismo distinto

Para fórmulas no se puede usar igual el argumento de diferenciación, porque la diferenciación eficiente se apoya precisamente en compartir subcálculos. Y una fórmula no comparte.

El walkthrough lo dice claro: una fórmula es un árbol; no puede reutilizar un cálculo intermedio. Por eso los métodos basados en multilinealidad sintáctica o diferenciación no daban la cota adecuada.

La IA usa una perspectiva tipo Nechiporuk algebraico.

Se elige un bloque de variables $𝑌$ y se expande:

$$𝑓(𝑌,𝑍)=\sum _{𝛼}{𝑐}_{𝛼}(𝑍){𝑌}^{𝛼}$$

Después se mide cuántos coeficientes ${𝑐}_{𝛼}(𝑍)$ son algebraicamente independientes. No importa solo cuántos coeficientes distintos hay, sino cuántos grados de libertad reales contienen. El paper lo mide mediante grado de trascendencia.

10. La intuición de la fórmula: los bloques de matching

La IA selecciona bloques $𝑌$ que son matchings cortos de entradas de la matriz. Un matching de tamaño logarítmico tiene dos ventajas:

• genera muchos coeficientes posibles;
• permite empaquetar muchos bloques disjuntos dentro de la matriz.

El walkthrough explica que un matching es mejor que tomar una fila completa: una fila da pocos bloques; bloques demasiado pequeños dan pocos coeficientes; bloques rectangulares grandes no se empaquetan bien. El matching logarítmico es el equilibrio correcto.

Luego se demuestra que cada bloque obliga a muchas hojas variables en la fórmula. Como los bloques elegidos son disjuntos en entradas de matriz, esas cargas se suman. Así aparece:

$${𝐿}_{\mathrm{v}\mathrm{a}\mathrm{r}}(\mathrm{\Phi })\ge \frac{{𝑛}^4}{128{\log }_2𝑛}$$

11. Cómo se maneja la división

Permitir divisiones parecía peligroso, porque una fórmula con división puede representar dependencias de forma más comprimida.

La IA adapta el argumento: en vez de ver las cadenas unarias como transformaciones afines,

$$𝑢\mapsto 𝐴(𝑍)𝑢+𝐵(𝑍)$$

las ve como transformaciones proyectivas/racionales:

$$𝑢\mapsto \frac{𝑎𝑢+𝑏}{𝑐𝑢+𝑑}$$

Cada punto de ramificación cuesta más parámetros, pero aún se puede controlar. El walkthrough explica que incluso matrices singulares deben permitirse, porque multiplicar por un subcálculo no marcado que vale cero puede ser legal. La identidad clave es que si el resultado final es polinómico, los coeficientes vuelven al campo correcto:

$$𝐾(𝑌)\cap 𝑅[𝑌]=𝐾[𝑌]$$

Con eso, la cota de orden ${𝑛}^4\mathrm{/}\log 𝑛$ sobrevive también con divisiones válidas.

12. Por qué no vale igual para el determinante

Esto es importante.

El permanente y el determinante se parecen formalmente, pero la prueba distingue sus mecanismos internos. El paper insiste en que ambos argumentos usan propiedades específicas del permanente y no implican directamente lo mismo para el determinante.

El walkthrough señala que, para el determinante, una especialización homogénea de grado mayor que dos tiene lugar crítico de codimensión como mucho $𝑛-1$, así que el método del gradiente solo daría $𝑂(𝑛\log 𝑛)$, incluso menos que la cota elemental cuadrática por dependencia de variables. También en fórmulas, los bloques del determinante no generan la misma riqueza cuadrática de coeficientes independientes que el permanente.

En síntesis:

el resultado no dice “todo polinomio matricial es difícil”; dice que el permanente tiene una estructura combinatoria especialmente difícil de comprimir.

13. Qué significa que lo haya hecho la IA

Según OpenAI, este resultado forma parte de los diez avances obtenidos por una versión interna de Astra, acompañados por manuscritos y formalizaciones en Lean. En el repositorio oficial aparece Permanent.lean como certificado asociado al resultado de complejidad de circuitos aritméticos.

La parte interesante no es solo el resultado, sino el tipo de descubrimiento:

la IA encuentra una ruta entre complejidad computacional, geometría algebraica, combinatoria de matchings y teoría de fórmulas.

No es fuerza bruta. Es cambio de representación.

14. Lectura RMS / pensamiento complejo

Este problema encaja muy bien con vuestra lógica RMS.

Recursos: permanente, variables de matriz, matchings, derivadas, fórmulas, circuitos, raíces de la unidad, coeficientes, campos racionales.

Mecanismos: reutilización de subcálculos, cancelación, codimensión crítica, diferenciación, Bézout, independencia algebraica, empaquetamiento de bloques.

Sistema: un modelo de cálculo donde la dificultad no está en una operación aislada, sino en la imposibilidad de comprimir simultáneamente una enorme red de dependencias combinatorias.

La clave sistémica sería:

El permanente es difícil no porque tenga muchos términos sin más, sino porque sus términos están conectados por una arquitectura de restricciones que resiste la reutilización, la cancelación y la factorización.

Síntesis final

La IA habría demostrado nuevas cotas inferiores para calcular el permanente. Para circuitos aritméticos sin división, prueba que hacen falta al menos $\mathrm{\Omega }({𝑛}^2\log \log 𝑛)$ puertas, superando la barrera elemental de ${𝑛}^2$ variables. 

Para fórmulas, demuestra una cota mucho más fuerte: $\mathrm{\Omega }({𝑛}^4\mathrm{/}\log 𝑛)$ hojas, incluso permitiendo divisiones válidas. La idea central fue traducir el problema de “cuántas operaciones hacen falta” a una mezcla de geometría algebraica y combinatoria: lugares críticos, codimensión, matchings, raíces de la unidad e independencia algebraica de coeficientes. 

En clave RMS, es otro ejemplo de IA descubriendo la arquitectura oculta del sistema, no simplemente haciendo más calculo

-----------------

8. Quantum parallel repetition
Teoría de juegos cuánticos y complejidad. La pregunta: si repites muchas veces un juego cuántico, ¿la probabilidad de ganar cae exponencialmente como en el caso clásico? OpenAI afirma un teorema de repetición paralela exponencial para juegos cuánticos bipartitos finitos.

 Los modelos matemáticos generados por IA comienzan a generar conocimiento científico original, verificable y económicamente barato.

https://articulosclaves.blogspot.com/2026/08/los-modelos-matematicos-generados-por.html