<p>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 <span class="math-container">$O(n^{2-e})$</span> time by multitape TMs, a longstanding open problem.</p>
<p>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.)</p>
<p>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!</p>
<hr />
<p>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 &quot;string pattern&quot; 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.</p>
<p>The set of &quot;string templates&quot; (the author's <span class="math-container">$U$</span>, Definition 5.1) is a set of strings over <span class="math-container">$\{0,1,end,branch\}$</span>, defined recursively:</p>
<ul>
<li><span class="math-container">$end \in U$</span></li>
<li><span class="math-container">$\alpha \in U$</span> implies <span class="math-container">$0\alpha, 1\alpha \in U$</span></li>
<li><span class="math-container">$\alpha, \beta \in U$</span> implies <span class="math-container">$branch~ \alpha \beta \in U$</span>.
Note that every string ends in an <span class="math-container">$end$</span> symbol. The <span class="math-container">$branch$</span> is used to denote a possible choice in the match: either <span class="math-container">$\alpha$</span> can be matched as a partial string, or <span class="math-container">$\beta$</span>, and <span class="math-container">$end$</span> is used at the end of <span class="math-container">$\alpha$</span> to signal where <span class="math-container">$\alpha$</span> ends and <span class="math-container">$\beta$</span> begins.</li>
</ul>
<p>We say that a binary string <span class="math-container">$x$</span> &quot;matches&quot; a string template <span class="math-container">$\alpha \in U$</span> (the author's Definition 5.2) if <span class="math-container">$x$</span> is in the set <span class="math-container">$\phi(\alpha)$</span>, recursively defined as:</p>
<ul>
<li><span class="math-container">$\phi(end) = \epsilon$</span> (<span class="math-container">$end$</span> symbols are removed)</li>
<li><span class="math-container">$\phi(b\alpha) = b \phi(\alpha)$</span> for <span class="math-container">$b \in \{0,1\}$</span> (normal string matching)</li>
<li><span class="math-container">$\phi(branch~ \alpha \beta) = 0\phi(\alpha) \cup 1 \phi(\beta)$</span>, for <span class="math-container">$\alpha,\beta \in U$</span>.
The third condition is the main one here: the author intends for us to find the <span class="math-container">$end$</span> symbol that &quot;matches up&quot; with the first <span class="math-container">$branch$</span> symbol, and partition <span class="math-container">$\alpha$</span> and <span class="math-container">$\beta$</span> according to that. Then, depending on whether the next symbol of <span class="math-container">$x$</span> is <span class="math-container">$0$</span> or <span class="math-container">$1$</span>, the next piece of <span class="math-container">$x$</span> should either partial-match to <span class="math-container">$\alpha$</span> or partial-match to <span class="math-container">$\beta$</span>.</li>
</ul>
<p>It should be analogous to think of an <span class="math-container">$\alpha$</span> as an encoding of a (rooted) binary tree (each node has at most two children), where we label each edge of the tree by <span class="math-container">$0$</span> or <span class="math-container">$1$</span>, and we say that a string <span class="math-container">$x$</span> matches the tree if there's some root-to-leaf path whose concatenated symbols are exactly <span class="math-container">$x$</span>.</p>
<p>Anyway, the final presumed hard function <span class="math-container">$g$</span> (Definition 5.2) is:</p>
<p><strong>Given a string template <span class="math-container">$\alpha \in U$</span> and given binary strings <span class="math-container">$x_1,\ldots,x_k$</span> (where each string is separated by a new symbol) output <span class="math-container">$k$</span> bits indicating which <span class="math-container">$x_i$</span>'s match the template <span class="math-container">$\alpha$</span>.</strong></p>
<p>If this was a &quot;normal&quot; partial match query problem (e.g. with strings over <span class="math-container">$\{0,1,\star\}$</span>, then it would be easily computed in <span class="math-container">$O(n)$</span> 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 <span class="math-container">$K$</span> paths down a binary tree of description size <span class="math-container">$N$</span> should take more than <span class="math-container">$(N+K) \cdot poly(\log(KN))$</span> 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 <em>a</em> journal: <a href="https://www.ems-ph.org/journals/show_pdf.php?issn=0034-5318&amp;vol=13&amp;iss=2&amp;rank=5" rel="nofollow noreferrer">https://www.ems-ph.org/journals/show_pdf.php?issn=0034-5318&amp;vol=13&amp;iss=2&amp;rank=5</a>) But I didn't spend more than an hour looking at this!</p>
<hr />
<p>FINAL UPDATE: Brynmor Chapman looked at this paper more closely, and observed the proof only gives a lower bound for the &quot;on line&quot; version of the function, where <strong>the query for each binary string <span class="math-container">$x_i$</span> (as described above) must be answered (the TM must output a bit) before the TM is allowed to read the next binary string <span class="math-container">$x_{i+1}$</span></strong>. This a data structure lower bound for TMs, which is much easier to prove given the 1-dimensional nature of TM tapes. <em><strong>That is, the lower bound proved is much weaker than what is claimed: that there is a function <span class="math-container">$g$</span> computable in linear time on RAMs which requires nearly quadratic time on a multi-tape Turing machine.</strong></em> As far as I know, that claim remains open.</p>

CC BY-SA 4.0
2020-11-09T05:05:49.507Z
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.
Michael Wehar
CC BY-SA 4.0
2020-11-09T05:06:30.923Z
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?
Michael Wehar
CC BY-SA 4.0
2020-11-09T05:28:42.213Z
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.
Ryan Williams
CC BY-SA 4.0
2020-11-09T08:10:58.490Z
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.
Michael Wehar
CC BY-SA 4.0
2020-11-09T09:06:04.110Z
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: https://epubs.siam.org/doi/10.1137/S0097539791223206, https://link.springer.com/article/10.1007/BF01205055 and https://epubs.siam.org/doi/10.1137/S0097539799360240
M. kanté
CC BY-SA 4.0
2020-11-09T01:48:21.067Z
2020-11-19T19:38:55.263Z
2020-11-19T19:38:55.263Z
Ryan Williams
<p><strong>Question:</strong> Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?</p>
<hr />
<p><strong>Background:</strong> I recently stumbled upon the dissertation &quot;Computational complexity of multitape Turning machines and Random Access Machines&quot; by Takumi Kasai (see here: <a href="https://repository.kulib.kyoto-u.ac.jp/dspace/handle/2433/86527" rel="noreferrer">https://repository.kulib.kyoto-u.ac.jp/dspace/handle/2433/86527</a>).</p>
<p>As far as I can tell, the author shows that there exists a function <span class="math-container">$g$</span> such that <span class="math-container">$g$</span> can be computed in <span class="math-container">$O(n)$</span> time by RAM machines, but cannot be computed in <span class="math-container">$O(n^{2-\varepsilon})$</span> time by Multitape Turing machines for all <span class="math-container">$\varepsilon &gt; 0$</span>.</p>
<p>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 <span class="math-container">$O(n)$</span> time by RAM machines that cannot be decided in <span class="math-container">$O(n^{2-\varepsilon})$</span> time by Multitape Turing machines for all <span class="math-container">$\varepsilon &gt; 0$</span>?</p>

CC BY-SA 4.0
2020-11-09T16:25:20.160Z
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)
Joshua
CC BY-SA 4.0
2020-11-09T16:56:13.280Z
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.
Ryan Williams
<cc.complexity-theory><time-complexity><lower-bounds><turing-machines><machine-models>
Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?
Michael Wehar
# Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

(Asked by: username_0 on 2020-11-08)

**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$?

**Tags:** cc.complexity-theory, time-complexity, lower-bounds, turing-machines, machine-models

> **Comments:**
> **username_1**: 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)  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_2 on 2020-11-09. Score: 11

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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?  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_3**: 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: https://epubs.siam.org/doi/10.1137/S0097539791223206, https://link.springer.com/article/10.1007/BF01205055 and https://epubs.siam.org/doi/10.1137/S0097539799360240  

---

