$\mbox{Problem}_{j,i,q}(x_1,\dots,x_n)$: Given an integer $\sum_{i''=0}^{n-1}2^{i''}x_{i''+1}$ in binary output the $j$th binary digit of the $i$th base-$q$ digit (where $q$ is not necessarily a prime).

$\mbox{Problem}_{j,i,q}(x_1,\dots,x_n)=j\mbox{ th bit of }y_i\mbox{ in }\sum_{i'=0}^{m-1}q^{i'}y_{i'+1}=\sum_{i''=0}^{n-1}2^{i''}x_{i''+1}$ where $y_{i'}\in\{0,1,\dots,q-1\}$ at every $i'\in\{1,\dots,m\}$ and $m=\lceil\log_q\sum_{i''=0}^{n-1}2^{i''}x_{i''+1}\rceil$.

Is $\mbox{Problem}_{j,i,q}(x_1,\dots,x_n)\in\mathsf{uniformTC^0}$ or at least $\mathsf{non-uniformTC^0}$?


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.