# Algorithm for idempotent algebra

A boolean algebra expression can be converted into an idempotent algebra using $$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$

where $$\otimes$$ is the idempotent product (no powers). For example, $$(a+b)\otimes(a-b) = a -ab +ab - b = a-b.$$

The CNF formula

$$\phi = (a\vee b) \; (b \vee c)(b \vee \bar c)(\bar b \vee \bar c) \; (a \vee c)(\bar a \vee \bar c)$$

can be converted into what I would call the idempotent expression $$\phi = (a + b - ab)\otimes (b-bc) \otimes (a+c-2ac).$$

This expression expands to give $$\phi = ab - abc$$. I would like an algorithm that, given a CNF formula as input, outputs the term with the lowest homogeneity. In this example, the oracle would return $$ab$$. (If there are multiple terms all with minimal homogeneity, the algorithm can return any one of them.)

Question 1: What is the complexity of this task? How high in the polynomial hierarchy is it?

Secondly, given a different idempotent expression $$\phi = ac+ad+bc+bd-abc-abd-2acd-2bcd + 2abcd,$$

I am interested in summing over the terms with equal homogeneity. By letting all variables be $$\epsilon$$ we get $$\phi = 4\epsilon ^2 - 6\epsilon^3 + 2\epsilon^4.$$ This yields a homogeneity vector of $$[0,0,4,-6,2]$$.

Question 2: What is the complexity of computing the homogeneity vector, given an idempotent expression as input? How high in the polynomial hierarchy is it?

• By the way, what you are interested in is sometimes called the multilinearization of a given polynomial (or expression evaluating to a polynomial). Dec 8 '19 at 12:06
• Just to make sure, explain how you convert a CNF to a polynomial (your example is not really clear). It seems that your polynomial is simply the unique multilinear polynomial with 0,1 inputs in which the 0,1 output encodes whether the input satisfies the formula (where 1 means True / Yes). Dec 8 '19 at 12:11
• @YuvalFilmus in such instances, either term would be sufficient. I call these idempotent expressions because any expression $E$ multiplied by itself gives $E$, hence all the expressions are idempotent. Dec 8 '19 at 12:11
• @YuvalFilmus take the 3rd factor $(a+c-2ac)$, this has come from $(a \vee c)\otimes(\bar a \vee \bar c).$ These factors can be written directly as $(a+c-ac) \otimes (1-ac)$ multiplying this through gives $(a+c-2ac)$. To go from the CNF form to the idempotent form I have simply multiplied together all clauses using the same pairs of variables. Dec 8 '19 at 12:19
– D.W.
Dec 8 '19 at 17:30

Let us consider the following decision version of your first problem:

Given a SAT instance, does its multilinear representation have a term of degree at most $$d$$?

I claim that this is the case iff the SAT instance has a satisfying assignment with at most $$d$$ ones.

Indeed, suppose first that $$m$$ is an inclusion-minimal term in the multilinear representation of the instance. Substituting 1 for the variables in $$m$$ and 0 for the variables outside of $$m$$, we get 1, that is, that the instance is satisfied. This shows that if the multilinear representation has a term of degree at most $$d$$, then the instance has a satisfying assignment with at most $$d$$ ones.

Now suppose that all terms in the multilinear representation have degree more than $$d$$. If we substitute any assignment with at most $$d$$ ones, then all monomials equal 0, and so the assignment falsifies the instance.

Therefore the decision version is equivalent to MIN-ONES-SAT, which is the following problem:

Given a SAT instance, does it have a satisfying assignment with at most $$d$$ ones?

The problem is in NP (it is easy to count the number of ones in a satisfying assignment), and it is clearly NP-hard (take $$d = n$$). Hence the problem is NP-complete.

Using an NP oracle, we can easily find a monomial with minimal degree, equivalently, a satisfying assignment with the least ones. Just substitute a 0 in one of the variables, and see if it increases the minimum weight of a solution. If so, set this variable to 1, otherwise set it to zero, and continue to the next variable. This answers your first question.

• As for your second question, the usual rule is one question per post. Dec 8 '19 at 12:36
• thank you for your time. I ask about the second question because I've proven that substituting the value $a=b=c=...=0.5$ then multiplying by $2^n$, with $n$ being the number of variables produces a solution to #SAT. That is, it produces the number of satisfying assignments. For $\phi = ab -abc$ we get $\#\phi = 2^3 \left( \frac{1}{4} - \frac{1}{8} \right) = 1$ Indeed, there is precisely 1 satisfying assingment. $ab\bar c$ Dec 8 '19 at 12:49
• Great, so your second task is $\#P$-hard. Since $\#P$ is quite powerful, one could conjecture that it's actually $\#P$-complete. Dec 8 '19 at 12:50
• Final question, have I discovered something trivial or something useful? Dec 8 '19 at 12:52
• Likely already known. It is certainly well-known that substituting $a = 1/2$ in a multilinear polynomial corresponds to averaging over $a \in \{0,1\}$. (Often we work over $\{ \pm 1\}$, in which case you'd substitute $a = 0$.) Dec 8 '19 at 12:54