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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.