0
$\begingroup$

finding the index of first zero entry in a binary string:

Input: binary string ($0$'s and $1$'s)

Output: index of first zero entry

Can you give a circuit for finding the index of first zero entry in a binary string with minimum depth and polynomial many processors?

1) Is this problem in $AC_0$?

2) Is this problem in $NC_1$?

Can point me at references?

$\endgroup$
  • $\begingroup$ 1) Yes. ​ 2) Yes. ​ ​ ​ What do you want the output to be on all-1 inputs? ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 May 18 '17 at 4:49
  • $\begingroup$ How can you build a circuit of AC_0? If all 1 inputs then nothing outputs. $\endgroup$ – GOLD May 18 '17 at 4:58
  • $\begingroup$ Start with an example: ​ If the input length is 6, then what positions of [first zero entry] will cause an output whose middle bit is 1? ​ ​ ​ ​ $\endgroup$ – user12859 May 18 '17 at 5:56
  • $\begingroup$ @RickyDemer Can you explain more clearly ? $\endgroup$ – GOLD May 18 '17 at 6:43
  • $\begingroup$ Would [a first zero entry being at index 0] cause an output whose middle bit is 1? ​ Would [a first zero entry being at index 1] cause an output whose middle bit is 1? ​ Would [a first zero entry being at index 2] cause an output whose middle bit is 1? ​ Would [a first zero entry being at index 3] cause an output whose middle bit is 1? ​ Would [a first zero entry being at index 4] cause an output whose middle bit is 1? ​ Would [a first zero entry being at index 5] cause an output whose middle bit is 1? ​ ​ ​ ​ $\endgroup$ – user12859 May 18 '17 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.