DNF Form of XOR Operator with N Arguments

Question

I’m working on this problem: Explain how to express $p$ using the boolean connectives AND, OR, and NOT so that the resulting expression has length polynomial in $n$.

$$p(x_1\cdots x_n) = x_1 \oplus x_2 \oplus\cdots \oplus x_n$$

where $\oplus$ is the exclusive-or operator.

I’ve created expressions for $n=3, n=4, n=5$ and $n=6$ in disjunctive normal form (DNF – so using only AND, OR, NOT) and see that the number of terms separated by an OR equals $2^{n-1}$.

Thus, I can see this general pattern in the growth of terms and in the composition of the terms themselves, especially with odd $n$’s and even $n$’s. I’m struggling though to create a generalized expression the XOR with multiple arguments and am slightly confused by the statement that is should have “length polynomial in $n$”.

If this refers to the number of OR separated terms once I reduce it as much as possible, this number will be much greater than $n$, namely $2^{n-1}$, so I don’t think that can be the correct interpretation.

Any guidance on how to think through this problem is greatly appreciated!

Answer 1

It seems the following.

Let $p(n; x_1,\dots, x_n)$ be XOR operator for $x_1,\dots, x_n$, $q(n; x_1, \dots, x_n)$ be XNOR operator for $x_1,\dots, x_n$. Then the required expressions of polynomial length follows from the recurrent formulas:

$$p(2^{n+1}; x_1, \dots, x_{2^{n+1}})=p(2^n; x_1,\dots, x_{2^n})\wedge q(2^n; x_{2^n+1},\dots, x_{2^{n+1}})\vee$$ $$q(2^n; x_1,\dots,x_{2^n})\wedge p(2^n; x_{2^n+1},\dots,x_{2^{n+1}}),$$

$$q(2^{n+1}; x_1,\dots,x_{2^{n+1}})=p(2^n; x_1,\dots,x_{2^n})\wedge p(2^n; x_{2^n+1},\dots, x_{2^{n+1}})\vee$$ $$q(2^n; x_1,\dots,x_{2^n})\wedge q(2^n; x_{2^n+1},\dots,x_{2^{n+1}}).$$

and $$ p(n; x_1\dots x_n)=p(2^k; x_1\dots x_n,0,\dots, 0),$$ where $k$ is the smallest integer such that $2^k\ge n$.

Answer 2

Suppose that $2^{k-1}<n\le 2^k$. If $n<2^k$, let $x_{n+1},\ldots,x_{2^k}$ be Boolean variables with truth value $F$; since $p(x_1,\ldots,x_n)$ is $T$ iff an odd number of the $x_i$ are $T$, it follows that

$$p(x_1,\ldots,x_n)=p(x_1,\ldots,x_{2^k})\;.$$

Now pair up the variables: for $i=1,\ldots,2^{k-1}$ let

$$x_i^{(1)}=x_{2i-1}\oplus x_{2i}=(x_{2i-1}\land\neg x_{2i})\lor(\neg x_{2i-1}\land x_{2i})\;;\tag{1}$$

clearly $p(x_1,\ldots,x_{2^k})=p(x_1^{(1)},\ldots,x_{2^{k-1}}^{(1)})$. The number of operands $x_i$ in $x_1\oplus\ldots\oplus x_{2^k}$ is of course $2^k$; the number in $x_1^{(1)}\oplus\ldots\oplus x_{2^{k-1}}^{(1)}$, when the variables are expanded using $(1)$, is $4\cdot2^{k-1}=2^{k+1}$.

After performing this pairing up a total of $k$ times, we have a single $x_1^{(k)}$ that expands to an expression using only $\land,\lor$, and $\neg$ and contains $2^{2k}$ operands $x_i$. Finally, $2^k<2n$, so $2^{2k}<4n^2$: the length in number of operands is bounded by a quadratic in $n$.