Algorithm for idempotent algebra

Question

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?

Answer 1

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.