Algorithme d'algèbre idempotente

Question

Une expression algébrique booléenne peut être convertie en une algèbre idempotente en utilisant $$ \ Bar A \ Equiv 1-a, \ Qquad A \ Vee B \ Equiv A + B -Ab, \ Qquad A \ Wedge B \ Equiv A \ Otimes B $$ < / span>

où $ \ otimes $ est le produit idempotent (pas de pouvoirs). Par exemple, $$ (A + B) \ OTIMES (A-B)= A -AB + AB - B= A-B. $$

La formule 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) $$

peut être converti en ce que j'appellerais l'expression idempotente $$ \ phi= (A + B - AB) \ Otimes (B-BC) \ Otimes (A + C-2AC). $$

Cette expression se dilate pour donner $ \ phi= ab - abc $ . Je voudrais un algorithme qui, étant donné une formule CNF comme entrée, génère le terme avec l'homogénéité la plus basse. Dans cet exemple, l'oracle retournerait $ ab $ . (Si plusieurs termes sont multiples avec une homogénéité minimale, l'algorithme peut renvoyer chacun d'entre eux.)

Question 1: Quelle est la complexité de cette tâche? Quelle est la hauteur de la hiérarchie polynomiale?

Deuxièmement, étant donné une autre expression idempotente différente $$ \ phi= AC + ad + bc + bd-abc-abd-2acd-2bcd + 2ABCD, $$ < / p>

Je suis intéressé par la somme des termes avec une homogénéité égale. En laissant toutes les variables être $ \ epsilon $ nous obtenons $$ \ Phi= 4 \ epsilon ^ 2 - 6 \ epsilon ^ 3 + 2 \ epsilon ^ 4. $$ Cela donne un vecteur d'homogénéité de $ [0,0,4, -6,2] $ .

Question 2: Quelle est la complexité du calcul du vecteur d'homogénéité, étant donné une expression idempotente comme entrée? Quelle est la hauteur de la hiérarchie polynomiale?

Answer 1

Considérons la version de décision suivante de votre premier problème:

Compte tenu d'une instance SAT, sa représentation multilinéaire a-t-elle un terme de degré au plus $ d $ ?

Je prétend que ceci est le cas IFF L'instance SAT a une affectation satisfaisante avec au plus $ d $

En effet, supposons d'abord que $ M $ est un terme minimal d'inclusion dans la représentation multilinéaire de l'instance. Substituant 1 pour les variables dans $ m $ et 0 pour les variables en dehors de $ m $ , nous obtenons 1, c'est-à-dire que l'instance est satisfaite. Cela montre que si la représentation multiligne a une durée de degré au plus $ d $ , l'instance a une affectation satisfaisante avec au plus $ d $ .

Supposons maintenant que tous les termes de la représentation multilinéaire ont degrés degré de plus que $ d $ . Si nous remplacons toute affectation avec au plus $ d $ , alors tous les monotis égaux 0, et la mission falsifie l'instance.

Par conséquent, la version de décision est équivalente à Min-One-Sat, qui est le problème suivant:

Compte tenu d'une instance SAT, a-t-il une affectation satisfaisante avec au plus $ d $

Le problème est dans NP (il est facile de compter le nombre de ceux dans une affectation satisfaisante), et il est clairement np-dur (prise $ d= n $ ). Par conséquent, le problème est NP-complet.

---

Utilisation d'un NP Oracle, nous pouvons facilement trouver un monôme avec un minimum de degré, de manière équivalente, une affectation satisfaisante avec les moins celles. Il suffit de substituer une 0 dans l'une des variables et de voir s'il augmente le poids minimum d'une solution. Si tel est le cas, définissez cette variable sur 1, sinon réglez-le à zéro et continuez à la variable suivante. Cela répond à votre première question.