2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ "I'm interested to know which parts are P and which parts are NP" P and NP are classes of decision problems: Given an instance $x$, answer "yes" or "no". This is a notion which is only tangential to transforming some object into another (equivalent) one. What you actually want to know is when your transformations blow up, which is pretty evident from simply counting the number of terms in each form in the example you have given. $\endgroup$ – dkaeae Jul 11 at 14:44
  • $\begingroup$ @dkaeae Thanks for the comment (I'm new to this as I'm sure you can tell) So presumably (CNF) $\rightarrow$ (AFF) is in P (AFF) $\rightarrow$ (EAF) is in NP (EAF) $\rightarrow$ (SEAF) is in P Or am I using P and NP incorrectly here? I have just finished a maths degree but only studied graph theory. So my apologies for not knowing the basics. $\endgroup$ – Ben Crossley Jul 11 at 14:52
  • 1
    $\begingroup$ As I've said, P and NP contain decision problems. Let me write a full-fledged answer to address that... $\endgroup$ – dkaeae Jul 11 at 15:00
  • $\begingroup$ @dkaeae Thank you, that is greatly appreciated $\endgroup$ – Ben Crossley Jul 11 at 15:06
1
$\begingroup$

$\mathsf{P}$ and $\mathsf{NP}$ are classes of decision problems. Essentially, a decision problem is a function $D \subseteq \{0,1\}^\ast \times \{ 0,1 \}$ (although describing $D$ simply by giving the subset $\{ 0,1 \}^\ast \times \{ 1 \}$ is more common). A Turing machine is said to solve $D$ if, given any string $x \in \{ 0,1 \}^\ast$, it produces $D(x)$. If there is a Turing machine which does so in time bounded by a polynomial $p(|x|)$, then $D \in \mathsf{P}$. If there is a nondeterminstic Turing machine capable of doing so in polynomial time, then $D \in \mathsf{NP}$. As you can see, $\mathsf{P}$ and $\mathsf{NP}$ are unrelated to transforming representations of objects into other (equivalent) representations; they are only about saying, for some string $x$, whether $D(x) = 1$ or not.

In your case, what we can do is analyze the time complexity of each transformation. The step CNF $\to$ AFF simply causes the formula to be longer by a constant factor and can be realized in linear time. In AFF $\to$ EAF, the formula blows up exponentially; assuming we previously had a maximum of $t$ terms for each of the $c$ clauses, you go over every possible $t^c$ multiplication of said terms, which takes potentially exponential time. The final EAF $\to$ SEAF step aggregates some terms and may be computed, for instance, in quadratic time (e.g., by looping over each term in the formula). Note that these time complexities are all relative to the respective input length for each step; for instance, "linear" is supposed to mean bounded by $c |\varphi|$, where $\varphi$ is the respective formula which is given as input to the respective transformation step.

I am not aware of a name for the forms you have given. Nevertheless, considering a Boolean formula $\varphi$ as an arithmetic expression (in particular over larger fields) is usually referred to as an arithmetization of $\varphi$ and is very relevant in complexity theory; see, for instance, this and this.

$\endgroup$
  • $\begingroup$ Thank you, that has cleared up a few things for me. I'm guessing then the fact that I can go straight from (SEAF) to the number of solutions and also extract all the solutions in polynomial time is nothing special? - That is, it is entirely useless $\endgroup$ – Ben Crossley Jul 11 at 15:38
  • 1
    $\begingroup$ Yes. You have essentially rediscovered that converting CNF to DNF allows efficiently determining the number of satisfiable assignments, only with an arithmetization step thrown in between. Indeed, reading the number of satisfiable assignments in a (reduced) DNF is trivial. The problem is that converting a CNF to a DNF results in a potentially exponential blowup in the formula size. $\endgroup$ – dkaeae Jul 11 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.