1
$\begingroup$

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

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

0

Your Answer

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

Browse other questions tagged or ask your own question.