0
$\begingroup$

Let's consider the language over $\{0,1\}$ containing such words $w$ that: $$w = m_1m_2..m_n $$ where $m_i$ has length $n$. (so $|w|=n^2$) and $$m_1 + m_2 + .. + m_n \mod 3 = 0$$

($m_i$ we interpret as binary encoded number).

Prove, that the language is $NC^1$ class.


The first problem is: How to decide whether $m_i$ is divisible by $3$?

$m_i = a_na_{n-1}...a_0$ where $a_i$ is a bit, so the number interpreted is: $v = a_0 \cdot 2^0 + a_1 \cdot 2 + .. + a_n \cdot 2^n$.

My only observation is:

$$2^{2k+1} \mod 3 = 1 \\ 2^{2k} \mod 3 = 2$$

Please hint me.

$\endgroup$
2
$\begingroup$

you have to use the fact that $2^n\mod 3 = n\mod 2 + 1$:

  • 2 mod 3 = 2
  • 4 mod 3 = 1
  • 8 mod 3 = 2
  • 16 mod 3 = 1
  • 32 mod 3 = 2

and so on.

The solution then for an $n$ bit number is to use $n$ processors, the $i$th processor will calculate $f_0(i) = i\mod 2 +1 * w[i]$ where w is the little-endian array of bits.

Then, each of the processors can calculate the following: $f_{t+1}(i) <= f_{t}(i) + f_{t}(i+2^t)\mod 3$, for $t \in \{1...log_2(n)\}$ (increasing sequentially of course). $f_{log_2(n)}(0)$ will then contain the sum of the bits mod 3.

$\endgroup$
  • $\begingroup$ And why is this in NC1? $\endgroup$ – Yuval Filmus Jul 30 '17 at 20:50
  • $\begingroup$ @Yuval Filmus, Thanks, changed to O(log^1(n)) instead of O(log^0(n)) $\endgroup$ – Aidan Connelly Jul 31 '17 at 10:05
1
$\begingroup$

The most direct way to show that this is in $\mathsf{NC}^1$ is through a "divide and conquer" approach.

First, we show how to compute $m\bmod{3}$ in $\mathsf{NC}^1$. The idea is to write $m = 2^h m_h + m_\ell$, where $m_h,m_\ell$ have roughly the same number of bits, compute $m_h,m_\ell \bmod{3}$, and combine the results.

After computing $m_i \bmod{3}$ for all $i$, we use a balanced binary tree to add (modulo 3) all these remainders. Then we can compare the result to 0. Details left to you.

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