Bridging across the \(\log(n)\) space frontier
type: Item
instance of: scholarly article
title: Bridging across the \(\log(n)\) space frontier
zbMATH Open document ID: 0917.68077
author: Viliam Geffert
published in: Information and Computation
publication date: 1998-11-10T00:00:00Z
review text: This paper establishes the importance of even the lowest possible level of space bounded computations. We show that DLOG does not coincide with NLOG if and only if there exists a tally set in \(\text{NSPACE}(\log\log n)\setminus\text{DSPACE}(\log \log n)\). This result stands in perfect analogy to the related results concerning linear space or exponential time. Moreover, the above problem is equivalent to the existence of a function \(s(n)\), with arbitrarily slow or rapid growth rate, that is nondeterministically fully space constructible but cannot be constructed deterministically. We also present a ``hardest'' fully space constructible \(s(n)\in O(\log\log n)\), a functional counterpart of log-space complete languages. These nonrelativized results are obtained by the use of oracle machines consuming much larger amount of space, in range between \(n\) and \(2^{d\cdot n}\).
reviewed by: Luisa Gargano
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 1221105
zbMATH Keywords: space bounded computations
MaRDI profile type: Publication
full work available at URL: inco.1997.2682
OpenAlex ID: W2059646261
cites work: Q3692869
cites work: A lower bound for the nondeterministic space complexity of context-free recognition
cites work: An optimal lower bound for nonregular languages
cites work: Strong optimal lower bounds for Turing machines that accept nonregular languages
cites work: The alternation hierarchy for sublogarithmic space is infinite
cites work: Space bounded computations: Review and new separation results
cites work: Inductive counting for width-restricted branching programs
cites work: Space bounds for processing contentless inputs
cites work: Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
cites work: Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
cites work: Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
cites work: A hierarchy that does not collapse : alternations in low level space
cites work: New developments in structural complexity theory
cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME
cites work: Q5636862
cites work: Some Results on Tape-Bounded Turing Machines
cites work: Q5592246
cites work: Nondeterministic Space is Closed under Complementation
cites work: ${\text{ASPACE}}(o(\log \log n))$ is Regular
cites work: Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\)
cites work: Q4281504
cites work: The Sublogarithmic Alternating Space World
cites work: Q3309910
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Halting space-bounded computations
cites work: The method of forced enumeration for nondeterministic automata
cites work: Some notes on strong and weak log log n space complexity
cites work: If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
cites work: Turing machines with sublogarithmic space
DOI: 10.1006/INCO.1997.2682
description: scientific article; zbMATH DE number 1221105