5
$\begingroup$

Savitch's theorem, 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 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?

Improve this question
$\endgroup$
3
  • 11
    $\begingroup$ Savitch's theorem is from 1970. The notion of completeness in complexity came up around the same time. $\endgroup$
    – Gamow
    Commented May 26, 2018 at 13:54
  • 1
    $\begingroup$ Not sure if this works, but could you construct a dummy problem from the TQBF that is NPSPACE complete? $\endgroup$
    – Konstantinos Koiliaris
    Commented May 26, 2018 at 14:36
  • 3
    $\begingroup$ 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. $\endgroup$
    – Thomas S
    Commented May 29, 2018 at 18:04

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.