Forme normale conjonctive à une algèbre élémentaire simple

Question

Je suis curieux de connaître la classe de complexité de calcul de chaque étape de cette méthode de conversion d'une formule CNF en algèbre élémentaire simple.

Un exemple:dollars $$Laisser $ neg a = 1-a $

Laisser $ a vee b = a + b-ab $

Laisser $ a wedge b = ab $

Alors:dollarsJe me réfère à cette étape comme une forme de facteur algébrique (AFF) (je ne suis pas familier avec une terminologie canonique) puis élargir ces supportsdollars ^ 2x_2x_3 ^ 2-x_1x_2 ^ 2x_3 ^ 2 + x_1 ^ 2x_2 ^ 2x_3 ^ 2 tag {eaf} $$Qui est sous forme d'algèbre élémentaire.

Enfin, en utilisant $ {x_1} ^ 2 = x_1, ; {x_2} ^ 2 = x_2, ; {x_3} ^ 2 = x_3 $ on a$$ phi = x_1- {x_1} + x_2 - 2x_1 x_2 + {x_1} x_2 + {x_1} x_3- {x_2} x_3 + 2x_1 {x_2} x_3-x_1x_2x_3-x_1x_2x_3 -x_1x_2x_3 +Qui simplifie:$$ phi = x_2 - x_1x_2 + x_1x_3 - x_2x_3 tag {seaf} $$Que j'appelle une forme d'algèbre élémentaire simple.

S'il y a déjà des noms établis pour ces formules, faites-le moi savoir et je modifierai dès que possible.

Ma question est donc: quelles sont les classes de complexité de calcul de chaque transformation en (CNF) $ rightarrow $ (Aff) $ rightarrow $ (EAF) $ rightarrow $ (Seaf)

Je suis intéressé à savoir quelles pièces sont P et quelles pièces sont np

Merci d'avance pour toutes les réponses, Ben