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?
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.