4
$\begingroup$

Consider the following problem:

Input: A binary string $w$.
Output: $|w|$ as a binary number.

Is it possible to compute this in $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$ (or equivalently in $\mathsf{AltTime}(O(1),O(\lg n))$ or $\mathsf{FO}$)?

$\endgroup$
  • 3
    $\begingroup$ The length of a string is outright computable in DLOGTIME in this setup (i.e., with input accessed through a query tape, not erased after each query). $\endgroup$ – Emil Jeřábek Feb 9 '16 at 17:16
  • $\begingroup$ However, I don't know what the answer would be for Rational-uniformity. ​ ​ $\endgroup$ – user6973 Feb 10 '16 at 15:58
  • $\begingroup$ @RickyDemer: The same. In fact, the finite automata implementing rational uniformity have the binary representation of the length of the input directly on one of their tapes by definition, so they don’t even need to compute it. $\endgroup$ – Emil Jeřábek Feb 10 '16 at 19:24
  • $\begingroup$ @EmilJerabek : ​ Yes,but can they output an AC0 circuit which will in turn output that length? ​ ​ ​ ​ $\endgroup$ – user6973 Feb 10 '16 at 19:33
6
$\begingroup$

Like Emil says, the answer is yes, because the length (in binary) of the input string is actually computable by a deterministic logtime Turing machine, so is a fortiori in $\mathsf{FO}$.

You may find this stated as Lemma 13 of Buss's The Boolean formula value problem is in ALOGTIME. The idea, attributed to Dowd, is to use the query tape to do binary search (under the convention that the machine gets an "out of range" response if the query tape contains a binary number exceeding the length of the input). I cut-and-paste the proof for quick reference (the number $n$ referenced in the proof is the length of the input, i.e., the desired output; the "index tape" is what Emil and I called query tape):

The [...] Turing machine proceeds as follows. First determine the least value of $i$ such that $n < 2^i$: this is easily done in $O(\log n)$ time since we assume that the index tape and its tape head are unaffected when the input tape is accessed. Once the value $2^i$ is obtained, written on the [index] tape, it is now easy to do a binary search to determine the value of $n$. Finally the index tape is copied to the output tape.

(NB: the paper actually says "Once the value $2^i$ is obtained, written on the input tape", etc., but it must be a typo, the computation described is obviously done by writing on the index/query tape. Besides, the input tape is usually read-only in this setting).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. :) I understand what Emil wrote. It feels that the machine's query tape mechanism is already doing this computation. In terms of FO it feels like saying that the language already contains $\mathsf{bit}$ relations and we can define the length of the input using the query $\mathsf{bit}(\max, i)$. I don't have $\mathsf{bit}(\max, i)$ in the language but it shouldn't matter because it is definable from order. I have to look at Immerman's book. $\endgroup$ – Kaveh Feb 10 '16 at 12:34
  • $\begingroup$ Immerman 98, p. 16 explains how to obtain $\mathsf{bit}$ from $\mathsf{plus}$ and $\mathsf{sum}$. $\mathsf{FO(wo\ bit)}$ (with order but without arithmetic) is equal to star-free $\mathsf{Reg}$ so it cannot define $\mathsf{bit}$. $\endgroup$ – Kaveh Feb 12 '16 at 16:42

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.