2
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ By the way, what you are interested in is sometimes called the multilinearization of a given polynomial (or expression evaluating to a polynomial). $\endgroup$
    – Yuval Filmus
    Dec 8, 2019 at 12:06
  • $\begingroup$ 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). $\endgroup$
    – Yuval Filmus
    Dec 8, 2019 at 12:11
  • $\begingroup$ @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. $\endgroup$
    – Ben Crossley
    Dec 8, 2019 at 12:11
  • $\begingroup$ @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. $\endgroup$
    – Ben Crossley
    Dec 8, 2019 at 12:19
  • $\begingroup$ Rather than leaving clarifications in the comments, please edit the question to address all of the feedback and questions you receive. We want people to be able to understand what you are asking without having to read the comments. I have taken the liberty of making some of those edits for you, so that you can see what I had in mind, but in the future, please do this yourself. I think it might help you get good answers. Thank you! $\endgroup$
    – D.W. ♦
    Dec 8, 2019 at 17:30

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ As for your second question, the usual rule is one question per post. $\endgroup$
    – Yuval Filmus
    Dec 8, 2019 at 12:36
  • $\begingroup$ 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$ $\endgroup$
    – Ben Crossley
    Dec 8, 2019 at 12:49
  • $\begingroup$ Great, so your second task is $\#P$-hard. Since $\#P$ is quite powerful, one could conjecture that it's actually $\#P$-complete. $\endgroup$
    – Yuval Filmus
    Dec 8, 2019 at 12:50
  • $\begingroup$ Final question, have I discovered something trivial or something useful? $\endgroup$
    – Ben Crossley
    Dec 8, 2019 at 12:52
  • 1
    $\begingroup$ 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$.) $\endgroup$
    – Yuval Filmus
    Dec 8, 2019 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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