Eliminación gaussiana en términos de acción grupal

La eliminación gaussiana hace que el determinante de una matriz de tiempo polinómico sea computable. La reducción de la complejidad en la computación del determinante, que de otro modo es la suma de términos exponenciales, se debe a la presencia de signos negativos alternativos (la falta de lo que hace que la computación sea permanente es $\#P\mbox{-}hard$ es decir, más difícil que los problemas $NP\mbox{-}C$ ) . Esto conduce a algún tipo de simetría en determinante, por ejemplo, el intercambio de un par de filas o columnas simplemente invierte los signos. Leí en alguna parte, probablemente en conexión con algoritmos holográficos introducidos por Valiant, que la eliminación gaussiana podría explicarse en términos de acción grupal y esto a su vez conduce a técnicas genéricas en la reducción de la complejidad.

Además, creo que casi todas las fuentes de reducción de la complejidad para cualquier problema computacional es una especie de simetría presente. ¿Es verdad? ¿Podemos formalizar esto rigurosamente en términos de teoría de grupos?

Editar

Encontré la referencia . (pg 2, última línea del segundo párrafo). No entendí el documento correctamente. Si mi pregunta se basa en una comprensión errónea del documento, corríjame.

En el caso del determinante, la eliminación gaussiana puede verse como equivalente a la idea de que el determinante tiene un gran grupo de simetría (de una forma particular) y se caracteriza por ese grupo de simetría (es decir, cualquier otro grado homogéneo polinomio en n 2 variables con esas simetrías debe ser un múltiplo escalar del determinante). (Y, en cuanto al punto de @Tsuyoshi Ito, parece que las simetrías del permanente no ayudan a calcularlo de manera eficiente: aunque el permanente también se caracteriza por sus simetrías, su grupo de simetría es mucho más pequeño que el del determinante).$n$$n^2$

Puede encontrar un resumen de esto, donde las simetrías del determinante se utilizan para eliminar Gauss, en el camino que demuestra que el determinante se caracteriza por sus simetrías, en la Proposición 3.4.3 de mi tesis (autoenchufe desvergonzado), pero Además, nunca lo había visto redactado de esta manera antes y escrito con todo detalle, como lo pedía el OP, aunque estoy seguro de que se ha hecho; estaría feliz si alguien tuviera otras referencias).

En cuanto a la idea de que la simetría siempre conduce a la reducción de la complejidad (o no), además de las cosas que ya están en los comentarios, vea esta pregunta y sus respuestas.

Un punto interesante es que en los primeros documentos de Valiant sobre lo que ahora se conoce como la versión de Valiant de la teoría de la complejidad algebraica, estaba tratando de señalar que una razón por la cual el determinante es importante computacionalmente es porque aproximadamente todos los (entonces) algoritmos eficientes conocidos podrían ser reducido a álgebra lineal y, por lo tanto, al cálculo del determinante, por ejemplo, el algoritmo FKT para contar coincidencias en gráficos planos. Esto es, por supuesto, una exageración, pero continúa siendo confirmado por la investigación de algoritmos holográficos, que a menudo se reducen a la computación de Pfaffian (un pariente cercano del determinante). Seguramente Valiant sabía que esto era una exageración, pero aquí está la cita exacta solo para asegurarse de que no estoy tergiversando ( L. Valiant. Clases de integridad en álgebra. ACM STOC 1979 ):

Nuestras principales conclusiones se pueden resumir aproximadamente de la siguiente manera:

(a) El álgebra lineal ofrece esencialmente la única técnica rápida para calcular polinomios multivariados de grado moderado

(b) ...

Hay casos en los que las simetrías de un problema (parecen) caracterizan su complejidad. Un ejemplo muy interesante son los problemas de satisfacción de restricciones (CSP).

Definición de CSP

Un CSP viene dado por un dominio y un lenguaje de restricción Γ ( k -ary funciona de U k a { 0 , 1 } ). Una instancia de satisfacción de restricciones viene dada por un conjunto de variables V y restricciones de $U$$\Gamma$$k$$U^k$$\{0, 1\}$$V$$\Gamma$$\phi:V \rightarrow U$

$\Gamma$$U$$\{0, 1\}$$\Gamma$$k$$U$$\{0, 1\}$ .

Polimorfismos

$\phi_1, \ldots, \phi_t$$f:U^t \rightarrow U$$\phi$$\phi(v) = f(\phi_1(v), \ldots, \phi_t(v))$$f$$t$

$f(x, y, z) = x + y + z \pmod 2$$f(x, x, y) = f(y, x, x) = y$$f$ que satisface esta propiedad se conoce como operación Maltsev. Los CSP que tienen un polimorfismo de Maltsev se pueden resolver mediante eliminación gaussiana.

$f(x, y) = x$

Polimorfismos y Complejidad (la conjetura de la dicotomía)

$\Gamma_1$$\Gamma_2$$\Gamma_1$$\Gamma_2$$\Gamma_2$$\Gamma_1$ es, de hecho, más difícil.

Un gran problema abierto en la teoría de la complejidad es caracterizar la dureza de los CSP. La conjetura de la dicotomía de Feder y Vardi establece que cualquier CSP está en P o NP completo. La conjetura se puede reducir a una declaración sobre polimorfismos: un CSP es NP-hard si y solo si los únicos polimorfismos que admite son "dictadores" (de lo contrario, está en P). Es decir, un CSP es difícil solo si no hay una forma local de formar soluciones nuevas genuinas a partir de soluciones antiguas. Se conoce la parte if (dureza), pero la única parte if (diseño de un algoritmo polytime) está abierta.

$U = \{0, 1\}$ , un CSP booleano está en P si admite uno de los 6 polimorfismos, de lo contrario es NP-completo. Los seis polimorfismos son básicamente lo que necesita para resolver el problema, ya sea por eliminación gaussiana o por propagación (como lo hace con horn-sat, por ejemplo), o para resolverlo mediante una tarea trivial.

Para leer más sobre polimorfismos, álgebra universal y la conjetura de la dicotomía, puede consultar la encuesta de Bulatov .

Polimorfismos y aproximabilidad

También recomiendo un conferencia IAS por Prasad Raghavendra donde expone su resultadodando una aproximabilidad óptima de cualquier CSP asumiendo la conjetura de juegos únicos en un marco similar. En un nivel alto, si todos los polimorfismos (esto necesita ser generalizado para manejar problemas de aproximación) de un CSP están cerca de los dictadores, uno puede usar el CSP para diseñar una forma de probar si una función es un dictador, y eso resulta sea ​​todo lo que necesita para ofrecer una dureza de reducción de aproximación de juegos únicos. Esto le da a la dureza la dirección de su resultado; la dirección algorítmica es que cuando un CSP tiene un polimorfismo que está lejos de ser un dictador, uno puede usar un principio de invariancia (generalización de los teoremas del límite central) para argumentar que un algoritmo de redondeo SDP da una buena aproximación. Una intuición realmente incompleta para la parte algorítmica: un polimorfismo que está lejos de ser un dictador no No importa si se proporciona como argumentos (una distribución sobre) asignaciones variables o variables aleatorias gaussianas que se aproximan localmente a una distribución sobre asignaciones variables. Esta es la misma forma en que una función de suma "no importa" si el teorema del límite central le da variables aleatorias discretas con una pequeña varianza o rv gaussianos con la misma varianza. Las variables aleatorias gaussianas que necesitamos pueden calcularse a partir de una relajación SDP del problema CSP. Entonces encontramos un polimorfismo que está lejos de ser un dictador, lo alimentamos con muestras gaussianas y recuperamos una buena solución. si se le dan variables aleatorias discretas con una pequeña varianza o rv gaussianos con la misma varianza, por el teorema del límite central. Las variables aleatorias gaussianas que necesitamos pueden calcularse a partir de una relajación SDP del problema CSP. Entonces encontramos un polimorfismo que está lejos de ser un dictador, lo alimentamos con muestras gaussianas y recuperamos una buena solución. si se le dan variables aleatorias discretas con una pequeña varianza o rv gaussianos con la misma varianza, por el teorema del límite central. Las variables aleatorias gaussianas que necesitamos pueden calcularse a partir de una relajación SDP del problema CSP. Entonces encontramos un polimorfismo que está lejos de ser un dictador, lo alimentamos con muestras gaussianas y recuperamos una buena solución.