1
$\begingroup$

I have 50 polynomials $f_i$ over binary variables $(x_1,\ldots,x_{100})$. Also $f_i(0,0,\ldots,0)=0$ for any $i \in [1,50]$. I want to assign few variables so that all $f_i$ will be identically zero. I want to assign number of variables as small as possible. Here assign means we will fix some variable either 0 or 1. Other will be binary variables. All are binary polynomial ring. If we fix all are zero, all polynomials will be zero identically. I want to reduce number of such assignment. Is there any way for this like using SMT etc? Kindly give your idea.

$\endgroup$
3
  • $\begingroup$ I don't know about efficiency, but you can get the answer from the primary decomposition of the ideal generated by $f_1,f_2,...,f_{50}$ in $\mathbb{F}_2[x_1,...,x_{100}]$. More specifically from the associated prime ideals or prime divisors of $I$. Some of the prime factors are generated by subsets of the variables, and among them some will have the minimum number of variables. There are algorithms to compute the associated primes from the generators of the ideal. Let me see if I find a link or a book that has the algorithm. $\endgroup$ – plop Feb 26 at 23:43
  • $\begingroup$ Well, I didn't make an exhaustive search. Primary factorization is a topic with a lot of research done. This is an article that talks about an algorithm to compute the minimal associated primes. The set of variables that you are looking for are the generators of one of the minimal primes associated to the ideal $I$. $\endgroup$ – plop Feb 26 at 23:56
  • $\begingroup$ Perhaps you want to find a subset of variables so that if you assign particular values to them, then all $f_i$ will be zero for all assignments of the other variables? Is that the goal? $\endgroup$ – D.W. Feb 27 at 0:37
0
$\begingroup$

I'll propose two algorithms.

SAT

Every binary multivariate polynomial $f$ can be represented in the form

$$f(x) = \sum_{S \in \mathcal{F}} \prod_{i \in S} x_i,$$

where $\mathcal{F}$ has one set per monomial of $f$, representing the variables included in that monomial. A multivariate function is identically zero iff all monomials have coefficient 0. So, we can express your problem as follows.

Let us represent the partial assignment by sets $M$, where $M$ indicates the set of variables that are are assigned and $v$ their values, and $\overline{M} = \{1,2,\dots,100\}\setminus M$ the complement of $M$. Then the condition is that after we make the partial assignment and simplify by collecting monomials, all monomials must have coefficient zero. This can be represented as

$$\Phi(M,v) = \bigwedge_{R \subseteq \overline{M}} \bigg[ \sum_{\substack{S \in F,\\S\cap \overline{M}=R}} \prod_{i \in S \cap M} v_i = 0 \bigg].$$

That's a huge logical formula, but it can be equivalently expressed with fewer clauses as

$$\Phi(M,v) = \bigwedge_{S \in \mathcal{F}} \bigg[ \sum_{\substack{T \in \mathcal{F},\\S\cap \overline{M}=T \cap \overline{M}}} \prod_{i \in S \cap M} v_i = 0 \bigg].$$

If $f$ has $n$ monomials, $\Psi(M,v)$ can thus be expressed as a sum of $n^2$ products of subsets of $v$. This can be expressed as a SAT formula of size $O(n^2)$, by introducing boolean variables to represent $M,v$ and applying the Tseitin transform.

Now your problem can be expressed as checking whether there exist $M,v$ such that

$$\Phi_1(M,v) \land \dots \land \Phi_{100}(M,v) \land |M| \le k,$$

where $\Phi_i(M,v)$ is the formula corresponding to requiring $f_i$ be identically zero. This can be checked with a SAT solver, and you can use binary search over $k$ to find the smallest $k$ for which this is satisfiable.

Unfortunately, if each $f_i$ has $n$ monomials, I suspect this will lead to a SAT instance with a small constant times $5000n^2$ CNF clauses, which sounds awfully large for existing SAT solvers to handle.

There are some optimizations that might make this more practical:

  • If we know that we are looking for an assignment to $k$ variables, the size of the formula for $\Phi(M,v)$ can be further reduced by additionally adding the constraint $|S \triangle T|\le k$ to the $T$'s we sum over, where $\triangle$ denotes the symmetric difference of sets.)

  • It might be helpful to use CryptoMiniSAT or some other SAT solver with built-in support for XOR (as each sum is a large XOR of boolean variables).

I'm not sure whether this will be enough to make your problem practically solvable in this way, though.

2QBF

We can formulate your problem as an instance of 2QBF as

$$\exists m, v . \text{wt}(m) \le k \land \forall w . f_1(m \;?\; v : w)=0 \land \dots \land f_{50}(m \;?\; v : w)=0,$$

where $m,v,w$ range over $\{0,1\}^{100}$, $k$ is a parameter, $\text{wt}(m)$ represents the Hamming weight of $m$ (the number of 1's in it), $m$ is a mask indicating which variables are assigned, $v$ indicates the values of the assigned variables, $w$ represents an assignment to the other variables, and

$$(m \;?\; v : w)_i = \begin{cases}v_i &\text{if }m_i=1\\ w_i &\text{if }m_i=0,\end{cases}$$

i.e., $m \;?\; v : w = (m \land v) \lor (\neg m \land w)$. If you can test satisfiability of this kind of 2QBF formula, you can use binary search over $k$ to find the minimum number of variables to assign to.

So, you could try applying standard algorithms for 2QBF to your problem. See https://cstheory.stackexchange.com/q/11022/5038. I don't know whether to expect that to be successful -- the problem size might be a bit large for this to work.

2QBF is harder than SAT and unlikely to be solvable with multiple queries to a SAT solver (see Is 2QBF in P^NP?).

$\endgroup$

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.