Given a constant $n\in\mathbb{N}_+$, is the simple power function $$ λ\,x\in\mathbb{N}_+.\,x^n $$ logspace computable by a logspace transducer (which has a read-only input tape, a working read-write tape (on which the transducer is allowed to use $\mathcal{O}(\log (\text{input size}))$) cells, and a write-only output tape), assuming that the input and the output are in binary? (It is not even clear to me how to do it for $n=2$ in logspace.) Any ideas or references?

  • $\begingroup$ How would it work in log space if the size of the output is exponential in the size of the input? I know you specified a transducer but still the computation will take exponential size to reach it. I am not saying it does not work I have no experience in that area but I find it very interesting if it works $\endgroup$ – narek Bojikian Oct 26 '19 at 19:02
  • $\begingroup$ @narekBojikian The size of the input is roughly $\log x$, whereas the size of the output is roughly $\log(x^n) = n\log x$, i.e., linear in the size of the input. $\endgroup$ – user111225 Oct 26 '19 at 20:15
  • $\begingroup$ Assuming n is a constant? $\endgroup$ – narek Bojikian Oct 26 '19 at 20:16
  • $\begingroup$ @narekBojikian Yes. The function to be computed has only $x$ as input, not $n$. I've just made an edit to emphasize this. $\endgroup$ – user111225 Oct 26 '19 at 20:17
  • $\begingroup$ But then the trivial method is already log space isnt it? I mean we never grow above the output and you said the output is small enouph $\endgroup$ – narek Bojikian Oct 26 '19 at 20:19

Yes, iterated multiplication is even in uniform TC0:

Hesse, William; Allender, Eric; Mix Barrington, David (2002). "Uniform constant-depth threshold circuits for division and iterated multiplication". Journal of Computer and System Sciences. 65: 695–716. doi:10.1016/S0022-0000(02)00025-9.

Explanation: We have TC0 ⊆ NC1 ⊆ L, where TC0 denotes the class of Boolean circuits with constant depth and polynomial size, where unbounded fan-in threshold gates are allowed, NC1 denotes the class of Boolean circuits with logarithmic depth and polynomial size, and L denotes logspace.

  • $\begingroup$ First, thanks. Second, is the a direct transducer description (rather a transducer evaluating a circuit), perhaps? Third, does your answer imply a positive solution for cs.stackexchange.com/questions/116253/… ? $\endgroup$ – user111225 Oct 27 '19 at 10:19
  • 1
    $\begingroup$ @MdAyq Since logspace is closed under composition, the well-known logspace multiplication variant of long multiplication should give you a more direct transducer description. The same argument (closure under composition) also implies a positive solution for that other question. But the transducer evaluating the composition is also ugly (= inefficient in terms of runtime) in a certain sense. $\endgroup$ – Thomas Klimpel Oct 27 '19 at 14:09
  • $\begingroup$ But isn't it the case that logspace multiplication produces the output starting from the least significant digit, whereas a logspace transducer is expected to output the most significant digit first? This is a non-issue if the logspace Turing machine can output from right to left, but it is an issue if it moves one-way, as usual, from left to right. $\endgroup$ – user111225 Oct 27 '19 at 15:49
  • 1
    $\begingroup$ @MdAyq A string can be reversed too by a logspace transducer. An again, because of that ulgy closure under composition, this is enough. $\endgroup$ – Thomas Klimpel Oct 27 '19 at 17:19
  • $\begingroup$ Yes, this gets ugly. I see that a direct transducer description (without logspace composition steps) is likely to be cumbersome. $\endgroup$ – user111225 Oct 27 '19 at 17:23

Your Answer

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