# Degrees of polynomials representing Boolean functions

Let $$B_1=\vee_{i_1=1}^d\wedge_{i_2=1}^d\dots\vee_{i_{2r-1}=1}^d\wedge_{i_{2r}=1}^dX_{i_1i_2\dots i_{2r-1}i_{2r}}$$ $$B_2=\wedge_{i_1=1}^d\vee_{i_2=1}^d\dots\wedge_{i_{2r-1}=1}^d\vee_{i_{2r}=1}^dX_{i_1i_2\dots i_{2r-1}i_{2r}}$$ be two boolean functions in $d^{2r}$ variables $X_{i_1i_2\dots i_{2r-1}i_{2r}}$ that take values in$\{0,1\}$.

Let $Z_0(B_i)$ be the set of $\{0,1\}^{d^{2r}}$-tuples that $B_i$ takes $0$. Let $Z_1(B_i)$ be the set of $\{0,1\}^{d^{2r}}$-tuples that $B_i$ takes $1$.

Let $f_1,f_2,g_1,g_2$ be polynomials in $d^{2r}$ variables that satisfy:

$(1)$ For every $z\in Z_0(B_i)$, $f_i(z)=g_i(z)=0$

$(2)$ For every $z\in Z_1(B_i)$, $f_i(z)=1$ and $g_i(z)\neq0$.

What is the smallest total degree of each $f_1,f_2,g_1,g_2$?

• formulas hard to parse. are you talking about CNF or DNF? – vzn Dec 2 '14 at 16:04
• $B_1$ is almost $\bar{B}_2$ except the variable $X_i$ are not complemented. – T.... Dec 2 '14 at 16:59