<p>A class that was more familiar at the time than <strong>NPSPACE</strong> was the class of context-sensitive languages.</p>
<p>Let <strong>CSL</strong> denote the set of context-sensitive languages. By Kuroda's theorem (1960), this set is equal to <span class="math-container">$\bf{NSPACE} (O(n))$</span>.</p>
<p>Log-lin-reducibility is logspace reducibility with the additional constraint that the size of the output string of the reduction is at most linear in the size of the input. The membership problem for context-sensitive grammars (or, if you like, linearly bounded automata) is the canonical CSL-complete problem w.r.t. log-lin reducibility.</p>
<p>The universality problem of (ordinary) regular expressions over binary alphabet, is CSL-complete w.r.t. log-lin-reducibility. The notion and the completeness result are found in Albert R. Meyer and Larry J. Stockmeyer (SWAT 1972) also: Stockmeyer (PhD thesis, MIT 1974).</p>
<p>This does not exactly predate Savitch's result, but it's off only one or two years - in the pre-internet era - and they did not build on his theorem. Also, I am not aware of other/previous usage of log-lin reductions or CSL- or NSPACE(n)-completeness results.</p>

CC BY-SA 4.0
2023-09-19T21:32:36.003Z
2023-09-20T14:50:13.817Z
2023-09-20T14:50:13.817Z
Hermann Gruber
<p><a href="https://www.sciencedirect.com/science/article/pii/S002200007080006X" rel="nofollow noreferrer">Savitch's theorem</a>, i.e. the fact that <span class="math-container">$NSPACE(f(n)^2) \subseteq DSPACE(f(n)^2)$</span> implies PSPACE = NPSPACE.</p>
<p>Using the idea of Savitch, <a href="https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/resources/mit18_404f20_lec17-1/" rel="nofollow noreferrer">Sipser proves in his lectures</a> that TQBF is PSPACE-complete.</p>
<p>What problems were known to be complete for NPSPACE before Savitch's discovery? What would be a natural logical language that could be shown complete for the class?</p>

CC BY-SA 4.0
2018-05-26T13:54:37.000Z
Savitch's theorem is from 1970. The notion of completeness in complexity came up around the same time.
Gamow
CC BY-SA 4.0
2018-05-26T14:36:56.397Z
Not sure if this works, but could you construct a dummy problem from the TQBF that is NPSPACE complete?
Konstantinos Koiliaris
CC BY-SA 4.0
2018-05-29T18:04:15.627Z
Not a “historically correct” answer, but maybe in spirit: the corridor tiling problem is somehow typical for NPSPACE, since for a direct solution nondeterminism is helpful and, on the other hand, it is easy to reduce from, say, linear-space bounded nondeterministic Turing machines to this problem.
Thomas S
<cc.complexity-theory><space-bounded><ho.history-overview><space-complexity>
Problems complete for non-deterministic PSPACE
Rajat De
# Problems complete for non-deterministic PSPACE

(Asked by: username_0 on 2018-05-26)

[Savitch's theorem](https://www.sciencedirect.com/science/article/pii/S002200007080006X), i.e. the fact that $NSPACE(f(n)^2) \subseteq DSPACE(f(n)^2)$ implies PSPACE = NPSPACE.

Using the idea of Savitch, [Sipser proves in his lectures](https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/resources/mit18_404f20_lec17-1/) that TQBF is PSPACE-complete.

What problems were known to be complete for NPSPACE before Savitch's discovery? What would be a natural logical language that could be shown complete for the class?

**Tags:** cc.complexity-theory, space-bounded, ho.history-overview, space-complexity

> **Comments:**
> **username_1**: Savitch's theorem is from 1970. The notion of completeness in complexity came up around the same time.  
> **username_2**: Not sure if this works, but could you construct a dummy problem from the TQBF that is NPSPACE complete?  
> **username_3**: Not a “historically correct” answer, but maybe in spirit: the corridor tiling problem is somehow typical for NPSPACE, since for a direct solution nondeterminism is helpful and, on the other hand, it is easy to reduce from, say, linear-space bounded nondeterministic Turing machines to this problem.  

---

## 1 answers

### Answer by username_4 on 2023-09-19. Score: 4

A class that was more familiar at the time than **NPSPACE** was the class of context-sensitive languages.

Let **CSL** denote the set of context-sensitive languages. By Kuroda's theorem (1960), this set is equal to $\bf{NSPACE} (O(n))$.

Log-lin-reducibility is logspace reducibility with the additional constraint that the size of the output string of the reduction is at most linear in the size of the input. The membership problem for context-sensitive grammars (or, if you like, linearly bounded automata) is the canonical CSL-complete problem w.r.t. log-lin reducibility.

The universality problem of (ordinary) regular expressions over binary alphabet, is CSL-complete w.r.t. log-lin-reducibility. The notion and the completeness result are found in Albert R. Meyer and Larry J. Stockmeyer (SWAT 1972) also: Stockmeyer (PhD thesis, MIT 1974).

This does not exactly predate Savitch's result, but it's off only one or two years - in the pre-internet era - and they did not build on his theorem. Also, I am not aware of other/previous usage of log-lin reductions or CSL- or NSPACE(n)-completeness results.


---

