¿Existe un concepto equivalente de "variedad" para SAT?

Question

No pude encontrar nada a través de google - Me preguntaba qué trabajo está ahí fuera mirando SAT problemas desde la perspectiva similar a una variedad algebraica, por ejemplo, un conjunto de variables$X_1=$ true,$X_2=$ false, .. ,% Definen un conjunto de proposiciones que son todas satisfechas por ese conjunto particular de valores de la misma manera que una variedad define un conjunto de polinomios que todos pasan a desaparecer en los mismos puntos.

Gracias.

Answer 1

En primer lugar, permítanme abordar la doble pregunta (que es fácil): visualización de un SAT instancia como una variedad.

No es una forma natural de representar cualquier instancia de SAT como una variedad en $(\mathbb{Z}/2\mathbb{Z})^n$ (donde $n$ es el número de variables). Esto es debido a que podemos interpretar los dos elementos del álgebra Booleana $(2, \vee, \wedge, \neg)$ en los dos elementos anillo de $(\mathbb{Z}/2\mathbb{Z}, +, \times)$:

• "$a\wedge b$" es la abreviatura de "$a\times b$".

• "$a\vee b$" es la abreviatura de "$a+b+ab$".

• "$\neg a$" es la abreviatura de "$1-a$" (es decir, el elemento del anillo de $\mathbb{Z}/2\mathbb{Z}$ que cuando se agrega a $a$ es igual a $1$). Tenga en cuenta que $1-a=1+a$ en este contexto.

Así, por ejemplo, para el SAT de instancia $$(a\vee b)\wedge (\neg a)$$ we associate the polynomial $$(a+b+ab)(1-a)=a+b+ab+a+ab+ab=b+ab.$$ Finding a solution to the SAT-instance corresponds to finding a point where this polynomial equals 1 (not zero), that is, to finding a zero for the polynomial $$1+b+ab.$$ It's easily checked that the only zero of this polynomial is $b=1$, $a=0$, lo cual está de acuerdo con el SAT de instancia.

Ver https://en.wikipedia.org/wiki/Boolean_ring.

---

OK, ahora en la cuestión de preguntar.

El problema es que en el fin de empezar a pensar en algo como una variedad, tenemos que pensar de esa cosa como un subconjunto de a $R^n$ para algunos ring $R$ y un número $n$. El problema es, el conjunto de SAT casos no se forma un anillo de una manera obvia (y no digamos el conjunto de los pares ordenados de un anillo).

Esto puede ser corregido: clases de equivalencia de SAT casos puede ser pensado como un anillo. Específicamente, identificar a $\varphi$ $\psi$ si sus conjuntos de soluciones son las mismas. El resultado es un álgebra de boole, que se puede transformar en un anillo Booleano (ver arriba). Ahora para cada valoración de la $k$-muchas variables proposicionales (arreglar $k$ antes de tiempo), podemos asociar un subconjunto de este anillo, y este subconjunto es de hecho una gran variedad. Pero esto es un poco feo; en particular, la clase de equivalencia de la construcción nos obliga a resolver SAT!

Basado en esto, me gustaría tentativamente decir que no es "natural" y computacionalmente eficiente manera de ver el conjunto de SAT casos que son resueltos por un fijo de valoración como una variedad.

Answer 2

Para una variedad de más de un campo finito, la geometría algebraica traducción de un SAT problema no es del todo útil. La conmutación entre las dos descripciones es computacionalmente trivial. La geometría algebraica no ayuda con la búsqueda de soluciones tanto como describir las relaciones entre las soluciones. Se SENTÓ problemas no conducen a estructurado de variedades como curvas elípticas o superficies algebraicas donde la geometría algebraica entra en su cuenta.

La ventaja de la geometría es cuando hay muchas variedades, o muchos campos y anillos en los que se resuelven las ecuaciones, o ambos.

Este es a grandes rasgos la idea de Aaronson y Wigderson del papel en Algebraization como una barrera a $P \neq NP$ pruebas. En General, los argumentos acerca de cómputo con bits, la idea de hechos acerca de polinomios o variedades donde buscamos soluciones mod $2$, también podría funcionar durante finito de los campos con más de $2$ elementos, o más en general de los anillos que eso. En aquellos más generales de la configuración se puede organizar oráculos para que $P = NP$, así que las cosas no son tan fáciles.

La Complejidad geométrica de la Teoría propuesta por Mulmuley es una aplicación de la geometría algebraica a la complejidad y una aproximación a la $P=NP$ problema, pero la geometría no viene de cartografía SAT problemas a ecuaciones algebraicas mod $2$. La idea es buscar algebraica de problemas en la teoría de invariantes y el grupo de teoría de la representación que están lo suficientemente cerca análogos de $P=NP$ que la solución de los problemas de álgebra tendría implicaciones para la teoría de la complejidad computacional. La geometría algebraica aparece en la GCT, porque es una herramienta para el álgebra de los problemas que aparecen.