Complejidad de minimizar el tamaño de la fórmula polinómica

Sea $f(x_1,\dots,x_n)$ un polinomio de grado en variables sobre , donde es constante (digamos 2 o 3). Me gustaría encontrar la fórmula más pequeña para , donde "fórmula" y "tamaño de fórmula" se definen de manera obvia (por ejemplo, la fórmula más pequeña para el polinomio es ).n F 2 d f x 1 x 2 + x 1 x 3 x 1 ( x 2 + x 3$d$$n$$\mathbb{F}_2$$d$$f$$x_1 x_2 + x_1 x_3$$x_1(x_2+x_3)$

¿Cuál es la complejidad de este problema? ¿Es NP-hard? ¿La complejidad depende de ?$d$

[Más formalmente, una fórmula (también conocida como "fórmula aritmética") es un árbol binario enraizado, cada una de cuyas hojas está etiquetada con una variable de entrada o la constante 1. Todos los demás vértices del árbol están etiquetados con o . El tamaño de la fórmula es el número de hojas utilizadas. La fórmula calcula un polinomio recursivamente: vértices calculan la suma de sus hijos sobre , vértices calculan el producto. ]× + F 2$+$$\times$$+$$\mathbb{F}_2$$\times$

Puede reducir el problema de la TAUTOLOGÍA co-NP-completa (dada una fórmula booleana, ¿es una tautología?) Al problema de minimizar el tamaño de la fórmula (ya que una fórmula es una tautología si es equivalente a VERDADERO). Además, la TAUTOLOGÍA para 3DNF (de forma análoga a SAT para 3CNF) es co-NP-completa.

No es exactamente la respuesta, pero con suerte ayuda:

Esta pregunta ya debería ser NP difícil para d = 2 si desea conocer la fórmula mínima para polinomios y no solo para uno. La prueba es la siguiente: existe una correspondencia uno a uno entre n fórmulas bi-lineales (fórmulas de tipo ∑ a i j x i y j ) y tensor 3 matrices, es decir, elementos en F n 2 ⊗ F n 2 ⊗ F n 2 . Tal rango de tensor de la matriz es exactamente la complejidad de multiplicación de n fórmulas bi-lineales.$n$$\sum a_{ij}x_iy_j$$F_2^n\otimes F_2^n\otimes F_2^n$

Se sabe que el rango tensor es un problema NP-duro (probablemente el rango tensor aproximado también es NP-duro). Por lo tanto, la complejidad de la multiplicación de n fórmulas bi-lineales es un problema NP-difícil$3$$n$

Cualquier respuesta a esto depende en gran medida del vocabulario que permita en la respuesta. Si desea su respuesta en el mismo idioma que la entrada (es decir, como un polinomio), eso lleva a un conjunto de respuestas, que es con lo que otros pósters han estado luchando.

Pero si permite que su vocabulario de respuestas se amplíe, pueden suceder cosas maravillosas. Puede ver un ejemplo en la diferenciación simbólica frente a la automática: en la diferenciación simbólica solo se permiten 'expresiones', que tienden a explotar bastante mal; En la diferenciación automática, se permiten programas en línea recta en la respuesta (incluso si la entrada era una expresión), lo que ayuda en gran medida a controlar el aumento de la expresión. Para polinomios univariados, James Davenport y yo hemos reflexionado que también necesita incluir polinomios ciclotómicos como parte de su vocabulario básico (vea las referencias de por qué estos polinomios parecen ser la única fuente real de explosión, así como los documentos que muestran varios resultados de reducibilidad entre problemas polinómicos y 3SAT).

En otras palabras, si te permites variar lo que consideras una respuesta un poco diferente de la clásica, es posible que puedas obtener una respuesta bastante diferente, es decir, una con una complejidad mucho mejor. Depende de su motivación original para hacer la pregunta, ya sea puramente teórica o con una aplicación en mente, decidir si esta variación en el vocabulario es aceptable para usted. En el entorno donde James y yo hemos estado pensando en esto (cálculo simbólico), ajustar el vocabulario para que la complejidad disminuya es perfectamente aceptable (aunque rara vez se hace).

La minimización general del circuito / fórmula es ciertamente más difícil que la prueba de identidad, ya que el tamaño mínimo de fórmula de cualquier identidad es simplemente cero. En cuanto a cuánto más difícil, no tengo una respuesta definitiva, pero tal vez los "algoritmos de reconstrucción" estudiados en circuitos / fórmulas aritméticas podrían ser algo así.

En estos casos, le dan una caja negra y le dicen que es una fórmula en alguna clase (digamos un circuito de profundidad 3 ). El objetivo es construir una representación de la caja negra en (algo parecido a) C . Por lo general, la mayoría de los resultados de reconstrucción suponen pruebas de identidad de caja negra para la clase, la aleatoriedad y, a veces, otros tipos de consultas. Tales algoritmos de reconstrucción están disponibles para ciertas clases restringidas de circuitos, pero no para todas las clases para las que conocemos PIT de blackbox. Shpilka y Yehudayoff tienen una encuesta fantástica (pdf) sobre circuitos aritméticos, y uno de los capítulos trata completamente sobre algoritmos de reconstrucción.$\mathcal{C}$$3$$\mathcal{C}$

$d$

$d=2$$x_1x_2 + x_3x_4 + .. + x_{2k-1}x_{2k} + \ell$