1
$\begingroup$

Given a natural number $n \geq 1$, I am looking for a Boolean circuit over $2n$ variables, $\varphi(x_1, y_1, \dots, x_n, y_n)$, such that the output is true if and only if the assignment that makes it true verifies

$$\sum_{i = 1}^{i = n} (x_i + y_i) \not\equiv n \bmod 3$$

I should specify that this I am looking for a Boolean circuit, not necessarily a Boolean formula as it is usually written in Conjunctive Normal Form (CNF). This is because when written in CNF, a formula like the one before has a trivial representation where the number of clauses is approximately $\frac{4^n}{3}$, as it contains a clause for every assignment $(x_1, y_1, \dots, x_n, y_n)$ whose bits sum to a value which is congruent with $n \bmod 3$. Constructing such a formula would therefore take exponential time.

I have been told that a Boolean circuit can be found for this formula that accepts a representation of size polynomial in $n$. However, so far I have been unable to find it. I would use some help; thanks.

$\endgroup$
1
$\begingroup$

Hint: Suppose you have a circuit with three outputs $s_0,s_1,s_2$ such that $s_k$ is true iff $\sum_{i=1}^{n-1} (x_i + y_i) \equiv k \mod 3$. Use these and $x_n, y_n$ to get $s'_0, s'_1, s'_2$ such that $s'_j$ is true iff $\sum_{i=1}^n (x_i + y_i) \equiv j \mod 3$.

$\endgroup$
1
  • $\begingroup$ Thank you so much! I think I got it; I'll try and write it down to make it clear. $\endgroup$ Jul 8 '19 at 21:51
0
$\begingroup$

So, following Robert Israel's hint (and more or less the same hint received at the Computer Science Stack Exchange), I've got the following:

You consider Boolean circuits $s_i^k$ over variables $(x_1, y_1, \dots, x_k, y_k)$, with $i \in \{0, 1, 2\}$ and $k \in \{1, \dots, n - 1\}$, such that $s_i^k$ is true if and only if $\sum_{j = 1}^k (x_i + y_i)\equiv i \bmod 3$.

With these circuits in hand, it is easy to obtain the corresponding circuits for $k = n$ (that is, $s_0^n$, $s_1^n$ and $s_2^n$):

$$s_0^n = (s_0^{n-1} \land \neg x_n \land \neg y_n) \lor (s_1^{n-1} \land x_n \land y_n) \lor (s_2^{n-1} \land (x_n \oplus y_n))$$ $$\dots$$

Now, you can obtain $\varphi(x_1, y_1, \dots, x_n, y_n) = \neg s_{n \bmod 3}^n$. Since we only have to build three new formulas for each value in $\{1, \dots, n\}$, each of which can be computed in constant time, we are able to build $\varphi$ in linear time.

With regards to the base cases, it is straightforward to see that: $$s_0^1 = \neg x_1 \land \neg y_1$$ $$s_1^1 = x_1 \oplus y_1$$ $$s_0^2 = x_1 \land y_1$$

$\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.