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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Possible duplicate of Algorithms computing if a number is a multiple of 3 $\endgroup$ Commented Jul 30, 2017 at 10:57
  • $\begingroup$ (I think your results modulo $3$ are reversed, $4^k=1[3]$ and $2 \times 4^k=2[3]$.) $\endgroup$ Commented Jul 30, 2017 at 14:17

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ And why is this in NC1? $\endgroup$ Commented Jul 30, 2017 at 20:50
  • $\begingroup$ @Yuval Filmus, Thanks, changed to O(log^1(n)) instead of O(log^0(n)) $\endgroup$ Commented Jul 31, 2017 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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.