14
$\begingroup$

Question: Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?


Background: I recently stumbled upon the dissertation "Computational complexity of multitape Turning machines and Random Access Machines" by Takumi Kasai (see here: https://repository.kulib.kyoto-u.ac.jp/dspace/handle/2433/86527).

As far as I can tell, the author shows that there exists a function $g$ such that $g$ can be computed in $O(n)$ time by RAM machines, but cannot be computed in $O(n^{2-\varepsilon})$ time by Multitape Turing machines for all $\varepsilon > 0$.

Can this result be extended to deciding languages (instead of computing functions)? In other words, can we prove that there is a language decidable in $O(n)$ time by RAM machines that cannot be decided in $O(n^{2-\varepsilon})$ time by Multitape Turing machines for all $\varepsilon > 0$?

$\endgroup$
2
  • 1
    $\begingroup$ I'm having trouble understanding why this question isn't trivial. Array join is very nearly linear on a RAM machine but can't be done any faster than quadratic than on a Turing machine. (Seek time) $\endgroup$
    – Joshua
    Nov 9 '20 at 16:25
  • 2
    $\begingroup$ I'm not exactly sure what you mean by "array join" but on a multitape Turing machine you can do lots of nontrivial stuff, including sorting in $O(n \cdot poly(\log n))$ time. $\endgroup$ Nov 9 '20 at 16:56
11
$\begingroup$

It depends on the precise definition of RAM being used, but (for most reasonable definitions of RAMs) this would also imply that SAT is not solvable in $O(n^{2-e})$ time by multitape TMs, a longstanding open problem.

The reason is that there is a very efficient reduction from linear time on RAMs to SAT (in general, nondeterministic quasi linear time on RAMs is the same as nondeterministic quasi linear time on multitape TMs.)

I have never seen the above reference before, and I would be skeptical if it never appeared in a journal or conference, but it could be worth checking to see if it implies a SAT lower bound as well. Interesting find!


UPDATE: I looked at the paper at your link above briefly this morning. The claimed hard function is a complicated partial match query problem. Essentially there is a notion of a "string pattern" and one is given a bunch of binary strings and asked to determine which strings fit the pattern (and which don't). Let me write out the definition of the function, as I understand it. I will use different symbols and terminology to try to make the definition easier to understand.

The set of "string templates" (the author's $U$, Definition 5.1) is a set of strings over $\{0,1,end,branch\}$, defined recursively:

  • $end \in U$
  • $\alpha \in U$ implies $0\alpha, 1\alpha \in U$
  • $\alpha, \beta \in U$ implies $branch~ \alpha \beta \in U$. Note that every string ends in an $end$ symbol. The $branch$ is used to denote a possible choice in the match: either $\alpha$ can be matched as a partial string, or $\beta$, and $end$ is used at the end of $\alpha$ to signal where $\alpha$ ends and $\beta$ begins.

We say that a binary string $x$ "matches" a string template $\alpha \in U$ (the author's Definition 5.2) if $x$ is in the set $\phi(\alpha)$, recursively defined as:

  • $\phi(end) = \epsilon$ ($end$ symbols are removed)
  • $\phi(b\alpha) = b \phi(\alpha)$ for $b \in \{0,1\}$ (normal string matching)
  • $\phi(branch~ \alpha \beta) = 0\phi(\alpha) \cup 1 \phi(\beta)$, for $\alpha,\beta \in U$. The third condition is the main one here: the author intends for us to find the $end$ symbol that "matches up" with the first $branch$ symbol, and partition $\alpha$ and $\beta$ according to that. Then, depending on whether the next symbol of $x$ is $0$ or $1$, the next piece of $x$ should either partial-match to $\alpha$ or partial-match to $\beta$.

It should be analogous to think of an $\alpha$ as an encoding of a (rooted) binary tree (each node has at most two children), where we label each edge of the tree by $0$ or $1$, and we say that a string $x$ matches the tree if there's some root-to-leaf path whose concatenated symbols are exactly $x$.

Anyway, the final presumed hard function $g$ (Definition 5.2) is:

Given a string template $\alpha \in U$ and given binary strings $x_1,\ldots,x_k$ (where each string is separated by a new symbol) output $k$ bits indicating which $x_i$'s match the template $\alpha$.

If this was a "normal" partial match query problem (e.g. with strings over $\{0,1,\star\}$, then it would be easily computed in $O(n)$ time on a multitape Turing machine, even one that just reads its input in one direction. I don't see why computing multiple queries on a binary search tree should take super-linear time for a multitape Turing machine. (I don't see why following $K$ paths down a binary tree of description size $N$ should take more than $(N+K) \cdot poly(\log(KN))$ time.) And the fact that it didn't appear in a major conference or a major journal makes me very suspicious. (It does appear in a journal: https://www.ems-ph.org/journals/show_pdf.php?issn=0034-5318&vol=13&iss=2&rank=5) But I didn't spend more than an hour looking at this!


FINAL UPDATE: Brynmor Chapman looked at this paper more closely, and observed the proof only gives a lower bound for the "on line" version of the function, where the query for each binary string $x_i$ (as described above) must be answered (the TM must output a bit) before the TM is allowed to read the next binary string $x_{i+1}$. This a data structure lower bound for TMs, which is much easier to prove given the 1-dimensional nature of TM tapes. That is, the lower bound proved is much weaker than what is claimed: that there is a function $g$ computable in linear time on RAMs which requires nearly quadratic time on a multi-tape Turing machine. As far as I know, that claim remains open.

$\endgroup$
5
  • $\begingroup$ Hi Ryan! Thank you for your answer. I think that I understand your point about if there is a language decidable in $O(n)$ time by RAM machines that cannot be decided in $O(n^{2-\varepsilon})$ time by Multitape Turing machines, then we would have lower bounds for SAT. This shows that a positive answer to my question would be as hard to show as proving lower bounds for SAT. $\endgroup$ Nov 9 '20 at 5:05
  • 2
    $\begingroup$ However, the result in the paper is for computing functions. I can't quite see how the existence of a function computable in $O(n)$ time by RAM machines that cannot be computed in $O(n^{2-\varepsilon})$ time by Multitape Turing machines would imply a lower bound for SAT. Would it? $\endgroup$ Nov 9 '20 at 5:06
  • 2
    $\begingroup$ The natural question is whether such a lower bound implies a lower bound for PRINTING a SAT assignment. I think it should. Probably the comment section here is not adequate for writing why. An n^(2-e) time lower bound for printing is known for small space for example (ITCS 2019) but this would arguably be much stronger. The reduction ideas in the ITCS paper should extend to this case as well. $\endgroup$ Nov 9 '20 at 5:28
  • 1
    $\begingroup$ Thinking about it, this seems reasonable to me. That is, if there exists a function computable in $O(n)$ time by RAM machines that cannot be computed in $O(n^{2-\varepsilon})$ time by Multitape Turing machines, then we would (probably) have lower bounds for Print-SAT. I am still not sure if we would have lower bounds for SAT though. $\endgroup$ Nov 9 '20 at 8:10
  • 2
    $\begingroup$ Just few words. I think the definition of RAM linear time in the thesis should be scrutinised and compared to Grandjean's definitions at least, which are believed strong: epubs.siam.org/doi/10.1137/S0097539791223206, link.springer.com/article/10.1007/BF01205055 and epubs.siam.org/doi/10.1137/S0097539799360240 $\endgroup$
    – M. kanté
    Nov 9 '20 at 9:06

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.