Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $M$ consist of the words in $\{0,1\}^{*}$, such that the number of $1$'s in $w$ is exactly $\lceil \log(n) \rceil$, where $n = |w|$.

a) Design a sequence of circuits $C_n$ recognizing $M$. $C_n$ should have polynomial size and depth $\mathcal O(\log(n))$

b) Classify $M$ in the classes $L$, $P$, $PSPACE$

We allow arbitrary fan-in for the $Or$ and $And$ gates.


I guess this can be done with just counting the number of $1$'s, as $\log(n)$ requires just $\log(\log(n))$ bits to be represented in binary?

share|improve this question
You answered part (b). Where are you stuck on part (a)? –  Yuval Filmus Apr 28 '11 at 2:11
Implementing a counter with circuits results in depth greater than O(logn) –  blu Apr 29 '11 at 6:51
This isn't true. Majority can be implemented in NC$^1$. In your particular case it might be easier since you only have to count up to $\log n$. –  Yuval Filmus Apr 29 '11 at 22:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.