A computational problem is said to be in the class $NC^K$, if the result $f(x)$ can be computed in time $O((\log |x|)^k )$ on a multi-processor computer, while the total number of operations remain polynomial in the input size $|x|$, i.e. number of bits in $x$. Show that counting the number of 1’s in a binary word $x \in \left\{0,1\right\}^{n}$ is an $NC^2$ problem. Hint: You may use a one-bit adder as a unit of counting.


Your function is in fact in $\mathsf{NC}^1$.

It is well-known that threshold functions are in $\mathsf{NC}^1$ (see for example this question on cstheory). In particular, the function $\sum_i x_i = w$ is in $\mathsf{NC}^1$ for all $w$. By computing these functions for all $w$, you can easily compute your function in $\mathsf{NC}^1$.

  • $\begingroup$ We have to use one-bit adder in counting how to do I am not getting but how to prove that it is NC^2 problem $\endgroup$ Oct 7 at 15:30
  • $\begingroup$ I'm sorry but I'm not willing to offer help of this kind. $\endgroup$ Oct 7 at 15:43

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.