<p>Here's one simple resolution. The statement referred to as "Fact 2" is a slightly weaker form of the standard <a href="https://en.wikipedia.org/wiki/Space_hierarchy_theorem" rel="nofollow noreferrer">Space Hierarchy Theorem</a>. The standard version of the Space Hierarchy Theorem has the quantifiers rearranged: </p>

<blockquote>
  <p>For every space-constructible <span class="math-container">$S_2(n)$</span>, there exists <span class="math-container">$L \in \mathbf{DSPACE}(S_2(n))$</span> such that for every space constructible
  <span class="math-container">$S_1(n) \leq o(S_2(n))$</span>, <span class="math-container">$L \not \in \mathbf{DSPACE}(S_1(n))$</span>.</p>
</blockquote>

CC BY-SA 4.0
2019-03-01T11:03:52.837Z
You mean they are actually using this theorem, hence this seems to be a typo in the paper?
StefanH
CC BY-SA 4.0
2019-03-02T22:30:25.757Z
Yes, I think that's a reasonable interpretation.
William Hoza
CC BY-SA 4.0
2019-03-01T07:38:25.733Z
2019-03-01T07:38:25.733Z
William Hoza
<p>My question concern's a statement from the classic paper <a href="http://www.cstheory.com/stockmeyer@sbcglobal.net/rsq.pdf" rel="nofollow noreferrer">The equivalence problem for regular expressions with squaring requires exponential space</a>.</p>

<p>Regular expressions with squaring are like ordinary regular expression but with a squaring operation. Let <span class="math-container">$RSQ(\Sigma) = \{ E \mbox{ is a regex with squaring} : L(E) \ne \Sigma^{\ast} \}$</span> be the test if some RegEx with squaring describes every word. In the paper the following is shown:</p>

<blockquote>
  <p>Theorem 2.1: There is a finite set <span class="math-container">$\Sigma$</span> such that if <span class="math-container">$M$</span> is any machine which recognizes <span class="math-container">$RSQ(\Sigma)$</span>, then there is a constant <span class="math-container">$c &gt; 1$</span> such that <span class="math-container">$M$</span> requires space (and hence time) <span class="math-container">$c^n$</span> on some input of length <span class="math-container">$n$</span> for infinitely many <span class="math-container">$n$</span>.</p>
</blockquote>

<p>By coding accepting computations by such regular expressions they continue to show that if <span class="math-container">$L \subseteq \{0,1\}^*$</span> is any language with a space bound of <span class="math-container">$2^n$</span>, then we can reduce the membership problem of <span class="math-container">$L$</span> to <span class="math-container">$RSQ(\Sigma)$</span> for some <span class="math-container">$\Sigma$</span> (the alphabet needs to be enlarged to account for describing sequences of instantaneous descriptions of Turing machines).</p>

<p>Then the argument for the above Theorem relies on the following fact (Fact 2 in the paper) taken from another paper:</p>

<blockquote>
  <p>Let <span class="math-container">$S_1(n)$</span>, <span class="math-container">$S_2(n)$</span> be tape constructable functions such that
  <span class="math-container">$$
 \inf_{n\to \infty} \frac{S_1(n)}{S_2(n)} = 0
\qquad \mbox{ and } S_2(n) \ge \log(n).
$$</span>
  Then there is a language <span class="math-container">$L \subseteq \{0,1\}^*$</span> accepted by some space <span class="math-container">$S_2(n)$</span> machine but by no space <span class="math-container">$S_1(n)$</span> machine.</p>
</blockquote>

<p>It is used in the following manner:</p>

<blockquote>
  <p><em>Proof of Theorem 2.1:</em> let <span class="math-container">$L$</span> be as in Fact 2 [the statement above] with <span class="math-container">$S_2(n) = 2^n$</span>. Let <span class="math-container">$\Sigma$</span> be such that <span class="math-container">$L$</span> reduces to <span class="math-container">$RSQ(\Sigma)$</span>.</p>
  
  <p>If <span class="math-container">$RSQ(\Sigma)$</span> is accepted by some space <span class="math-container">$S(n)$</span> machine, then <span class="math-container">$L$</span> is accepted by some space <span class="math-container">$S(cn) + cn$</span> machine for some constant <span class="math-container">$c$</span> [this is a general property of reductions as stated earlier].
  <span class="math-container">$$
 \inf_{n\to \infty} \frac{S(cn) + cn}{2^n} &gt; 0 
$$</span>
  implies that <span class="math-container">$S(n) \ge d^n$</span> for some constant <span class="math-container">$d &gt; 1$</span> and all <span class="math-container">$n$</span> which are multiples of <span class="math-container">$c$</span>.</p>
</blockquote>

<p>How do they know that <span class="math-container">$\inf_{n\to \infty} \frac{S(cn) + cn}{2^n} &gt; 0$</span>? Somehow the order of quantifiers in the statement of the fact seem not to match that kind of deduction. It does not say that if we have any machine with <span class="math-container">$S'(n)$</span> which also accepts <span class="math-container">$L$</span> then we must have 
<span class="math-container">$$
 \inf_{n\to \infty} \frac{S'(n)}{S(n)} &gt; 0.
$$</span>
It just says that if this equals zero, then we can choose some language accepted in space bound <span class="math-container">$S(n)$</span> but not in space bound <span class="math-container">$S'(n)$</span>, so it depends on the firstly choosen <span class="math-container">$S'(n)$</span>. But the argument of the proof does not seem to use it that way. Also the introduction "Let <span class="math-container">$L$</span> be as in Fact 2 [...]" seems problematic, for what space bound function <span class="math-container">$S'(n)$</span> in the numerator is <span class="math-container">$L$</span> choosen?</p>

<p>So how do this argument works? What am I missing here? Can someone please explain?</p>

<p><em>EDIT</em>: Just let me add that if I accept <span class="math-container">$\inf_{n\to \infty} \frac{S(cn) + cn}{2^n} &gt; 0$</span> then <span class="math-container">$S(n) \ge d^n$</span> for some <span class="math-container">$d &gt; 1$</span> and all multiplies of <span class="math-container">$c$</span> is clear to me. For then we know for some <span class="math-container">$\varepsilon &gt; 0$</span> we have
<span class="math-container">$$
 S(cn) &gt; 2^n\varepsilon - cn
$$</span>
for all <span class="math-container">$n &gt; N$</span> for some <span class="math-container">$N$</span>. Write with <span class="math-container">$d &gt; 1$</span> then <span class="math-container">$2^n = (d + \delta)^n \ge d^n + n d^{n-1}\delta \ge d^n +
 d^{n-1}\delta$</span> and as <span class="math-container">$\lim_{n\to \infty} \frac{c\varepsilon^{-1}n}{d^{n-1}} = 0$</span> we have <span class="math-container">$c\varepsilon^{-1}n \le d^{n-1}\delta$</span> for all <span class="math-container">$n$</span> sufficiently large, which gives <span class="math-container">$S(cn) \ge \varepsilon d^n$</span>. Now choose <span class="math-container">$1 &lt; \hat d &lt; d$</span> and we find <span class="math-container">$\lim_{n\to \infty} \frac{\hat d^n}{\varepsilon d^n} = 0$</span>, hence <span class="math-container">$\varepsilon d^n \ge \hat d^n$</span> for sufficiently large <span class="math-container">$n$</span>. So understanding the following conclusions is not the problem.</p>

<cc.complexity-theory><space-bounded><exp-time-algorithms><space-complexity>
Question on deduction that a certain problem requires exponential space
StefanH
# Question on deduction that a certain problem requires exponential space

(Asked by: username_0 on 2019-02-27)

My question concern's a statement from the classic paper [The equivalence problem for regular expressions with squaring requires exponential space](http://www.cstheory.com/stockmeyer@sbcglobal.net/rsq.pdf).

Regular expressions with squaring are like ordinary regular expression but with a squaring operation. Let $RSQ(\Sigma) = \{ E \mbox{ is a regex with squaring} : L(E) \ne \Sigma^{\ast} \}$ be the test if some RegEx with squaring describes every word. In the paper the following is shown:

> Theorem 2.1: There is a finite set $\Sigma$ such that if $M$ is any machine which recognizes $RSQ(\Sigma)$, then there is a constant $c > 1$ such that $M$ requires space (and hence time) $c^n$ on some input of length $n$ for infinitely many $n$.

By coding accepting computations by such regular expressions they continue to show that if $L \subseteq \{0,1\}^\*$ is any language with a space bound of $2^n$, then we can reduce the membership problem of $L$ to $RSQ(\Sigma)$ for some $\Sigma$ (the alphabet needs to be enlarged to account for describing sequences of instantaneous descriptions of Turing machines).

Then the argument for the above Theorem relies on the following fact (Fact 2 in the paper) taken from another paper:

> Let $S\_1(n)$, $S\_2(n)$ be tape constructable functions such that
> $$
> \inf\_{n\to \infty} \frac{S\_1(n)}{S\_2(n)} = 0
> \qquad \mbox{ and } S\_2(n) \ge \log(n).
> $$
> Then there is a language $L \subseteq \{0,1\}^\*$ accepted by some space $S\_2(n)$ machine but by no space $S\_1(n)$ machine.

It is used in the following manner:

> *Proof of Theorem 2.1:* let $L$ be as in Fact 2 [the statement above] with $S\_2(n) = 2^n$. Let $\Sigma$ be such that $L$ reduces to $RSQ(\Sigma)$.
>
> If $RSQ(\Sigma)$ is accepted by some space $S(n)$ machine, then $L$ is accepted by some space $S(cn) + cn$ machine for some constant $c$ [this is a general property of reductions as stated earlier].
> $$
> \inf\_{n\to \infty} \frac{S(cn) + cn}{2^n} > 0
> $$
> implies that $S(n) \ge d^n$ for some constant $d > 1$ and all $n$ which are multiples of $c$.

How do they know that $\inf\_{n\to \infty} \frac{S(cn) + cn}{2^n} > 0$? Somehow the order of quantifiers in the statement of the fact seem not to match that kind of deduction. It does not say that if we have any machine with $S'(n)$ which also accepts $L$ then we must have
$$
\inf\_{n\to \infty} \frac{S'(n)}{S(n)} > 0.
$$
It just says that if this equals zero, then we can choose some language accepted in space bound $S(n)$ but not in space bound $S'(n)$, so it depends on the firstly choosen $S'(n)$. But the argument of the proof does not seem to use it that way. Also the introduction "Let $L$ be as in Fact 2 [...]" seems problematic, for what space bound function $S'(n)$ in the numerator is $L$ choosen?

So how do this argument works? What am I missing here? Can someone please explain?

*EDIT*: Just let me add that if I accept $\inf\_{n\to \infty} \frac{S(cn) + cn}{2^n} > 0$ then $S(n) \ge d^n$ for some $d > 1$ and all multiplies of $c$ is clear to me. For then we know for some $\varepsilon > 0$ we have
$$
S(cn) > 2^n\varepsilon - cn
$$
for all $n > N$ for some $N$. Write with $d > 1$ then $2^n = (d + \delta)^n \ge d^n + n d^{n-1}\delta \ge d^n +
d^{n-1}\delta$ and as $\lim\_{n\to \infty} \frac{c\varepsilon^{-1}n}{d^{n-1}} = 0$ we have $c\varepsilon^{-1}n \le d^{n-1}\delta$ for all $n$ sufficiently large, which gives $S(cn) \ge \varepsilon d^n$. Now choose $1 < \hat d < d$ and we find $\lim\_{n\to \infty} \frac{\hat d^n}{\varepsilon d^n} = 0$, hence $\varepsilon d^n \ge \hat d^n$ for sufficiently large $n$. So understanding the following conclusions is not the problem.

**Tags:** cc.complexity-theory, space-bounded, exp-time-algorithms, space-complexity

---

## 1 answers

### Answer by username_1 on 2019-03-01. Score: 2 | Accepted answer

Here's one simple resolution. The statement referred to as "Fact 2" is a slightly weaker form of the standard [Space Hierarchy Theorem](https://en.wikipedia.org/wiki/Space_hierarchy_theorem). The standard version of the Space Hierarchy Theorem has the quantifiers rearranged:

> For every space-constructible $S\_2(n)$, there exists $L \in \mathbf{DSPACE}(S\_2(n))$ such that for every space constructible
> $S\_1(n) \leq o(S\_2(n))$, $L \not \in \mathbf{DSPACE}(S\_1(n))$.

> **Comments:**
> **username_0**: You mean they are actually using this theorem, hence this seems to be a typo in the paper?  
> **username_1**: Yes, I think that's a reasonable interpretation.  

---

