Conjunctive normal form to simple elementary algebra
-
05-11-2019 - |
Question
I'm curious to know the computational complexity class of each step in this method of converting a CNF formula into simple elementary algebra.
An example: $$\phi=\left(x_1 \vee x_2 \right) \wedge \left(\neg x_1 \vee x_3 \right) \wedge \left(\neg x_2 \vee \neg x_3 \right) \tag{CNF} $$ Let $\neg a = 1-a$
Let $a \vee b= a+b-ab$
Let $a \wedge b = ab$
Then: $$\phi=\left(x_1 + x_2 -x_1x_2\right) \left(1-x_1+x_1x_3\right) \left(1-x_2x_3 \right) \tag{AFF} $$ I refer to this step as algebraic factor form (AFF) (I am unfamiliar with any canonical terminology) Then expanding these brackets out gives $$\phi = x_1-{x_1}^2+x_2 - 2x_1 x_2 +{x_1}^2x_2 + {x_1}^2x_3-{x_2}^2x_3+2x_1{x_2}^2x_3-x_1^2x_2^2x_3-x_1^2x_2x_3^2-x_1x_2^2x_3^2 + x_1^2x_2^2x_3^2 \tag{EAF}$$ Which is in elementary algebra form.
Finally, using ${x_1}^2=x_1, \; \; {x_2}^2=x_2, \; \; {x_3}^2=x_3$ we get $$\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 + x_1x_2x_3$$ Which simplifies to: $$\phi = x_2 - x_1x_2 + x_1x_3 - x_2x_3 \tag{SEAF}$$ Which I call simple elementary algebra form.
If there are already established names for these formulas please let me know and I will amend asap.
So my question is: What are the computational complexity classes of each transformation in (CNF) $\rightarrow$ (AFF) $\rightarrow$ (EAF) $\rightarrow$ (SEAF)
I'm interested to know which parts are P and which parts are NP
Thanks in advance for any answers, Ben
No correct solution