Algoritmo para álgebra idempotente

Question

Una expresión de álgebra booleana se puede convertir en un álgebra idempotente usando $$ \ bar A \ Equiv 1-A, \ QQuad A \ Vee B \ Equiv A + B -AB, \ QQuad A \ Wedge B \ Equiv A \ Otimes B $$ < / span>

Donde $ \ Otimes $ es el producto idempotente (sin poderes). Por ejemplo, $$ (A + B) \ OTIMES (A-B)= A -AB + AB - B= A-B. $$

La fórmula CNF

$$ \ PHI= (A \ Vee B) \; (b \ vee c) (b \ vee \ bar c) (\ bar b \ vee \ bar c) \; (A \ Vee C) (\ Bar A \ Vee \ Bar c) $$

se puede convertir en lo que llamaría la expresión idempotente $$ \ PHI= (A + B - AB) \ Otimes (B-BC) \ Otimes (A + C-2AC). $$

Esta expresión se expande para dar $ \ phi= ab - abc $ . Me gustaría un algoritmo que, dado una fórmula CNF como entrada, emite el término con la homogeneidad más baja. En este ejemplo, el Oracle devolvería $ Ab $ . (Si hay múltiples términos con una homogeneidad mínima, el algoritmo puede devolver cualquiera de ellos).

Pregunta 1: ¿Cuál es la complejidad de esta tarea? ¿Qué tan alto en la jerarquía polinomial es?

en segundo lugar, dada una expresión idempotente diferente $$ \ PHI= AC + AD + BC + BD-ABC-ABD-2ACD-2BCD + 2ABCD, $$ < / p>

Estoy interesado en resumir sobre los términos con igual homogeneidad. Al permitir que todas las variables sean $ \ Epsilon $ obtenemos $$ \ PHI= 4 \ Epsilon ^ 3 + 2 \ Epsilon ^ 3 + 2 \ Epsilon ^ 4. $$ Esto produce un vector de homogeneidad de $ [0,0,4, -6,2] $ .

Pregunta 2: ¿Cuál es la complejidad de computar el vector de homogeneidad, dada una expresión idempotente como entrada? ¿Qué tan alto en la jerarquía polinomial es?

Answer 1

Consideremos la siguiente versión de decisión de su primer problema:

Dada una instancia de SAT, ¿su representación multilínea tiene un término de grado en la mayoría de $ d $ ?

Afirmo que este es el caso de la IFF, la instancia SAT tiene una tarea satisfactoria con la mayoría de $ d $ .

De hecho, supongamos primero que $ m $ es un término mínimo de inclusión en la representación multiliaguda de la instancia. Sustituyendo 1 para las variables en $ m $ y 0 para las variables fuera de $ m $ , obtenemos 1, es decir, que la instancia está satisfecha. Esto muestra que si la representación multilínea tiene un término de grado en la mayoría de $ d $ , entonces la instancia tiene una asignación satisfactoria con la mayoría de $ d $ .

Ahora suponga que todos los términos en la representación multilínea tienen más que el grado más que $ d $ . Si sustituimos cualquier asignación con la mayoría de $ d $ , todos los monomiales iguales 0, por lo que la asignación falsifica la instancia.

Por lo tanto, la versión de decisión es equivalente a Min-ONE-SAT, que es el siguiente problema:

Dada una instancia de SAT, ¿tiene una tarea satisfactoria con la mayoría de $ d $ ?

El problema está en NP (es fácil contar el número de uno en una asignación satisfactoria), y es claramente NP-HARD (Tomar $ d= n $ ). Por lo tanto, el problema es NP-Completo.

---

Usando un NP Oracle, podemos encontrar fácilmente un monomio con un grado mínimo, equivalente, una asignación satisfactoria con los menos. Simplemente sustituya a 0 en una de las variables, y vea si aumenta el peso mínimo de una solución. Si es así, configure esta variable a 1, de lo contrario, configúrela a cero, y continúe con la siguiente variable. Esto responde a tu primera pregunta.