A survey of space complexity
From MaRDI portal
Publication:1193412
DOI10.1016/0304-3975(92)90151-5zbMath0780.68042OpenAlexW1981296138MaRDI QIDQ1193412
Publication date: 27 September 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(92)90151-5
Cites Work
- New developments in structural complexity theory
- If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
- Space-bounded hierarchies and probabilistic computations
- Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\)
- On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
- Erratum to: Some observations concerning alternating Turing machines using small space
- The method of forced enumeration for nondeterministic automata
- The problem of space invariance for sequential machines
- Remarks on languages acceptable in log log n space
- There are no fully space constructible functions between log log n and log n
- Relativized alternation and space-bounded computation
- A measure of relativized space which is faithful with respect to depth
- Space measures for storage modification machines
- Halting space-bounded computations
- Deterministic simulation of tape-bounded probabilistic Turing machine transducers
- An extension of Savitch's theorem to small space bounds
- On uniform circuit complexity
- On tape-bounded probabilistic Turing machine acceptors
- Space complexity in on-line computation
- On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
- Space bounds for processing contentless inputs
- The network complexity and the Turing machine complexity of finite functions
- On tape bounds for single letter alphabet language processing
- Techniques for separating space complexity classes
- Relating refined space complexity classes
- On languages accepted by space-bounded oracle machines
- Some notes on strong and weak log log n space complexity
- Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
- Randomised algorithms
- Relationships between nondeterministic and deterministic tape complexities
- Approximate formulas for some functions of prime numbers
- A note on relativized log space
- Alternating Pushdown and Stack Automata
- Uniform characterizations of non-uniform complexity measures
- There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- On efficient deterministic simulation of turing machine computations below logaspace
- On the power of two-way random generators and the impossibility of deterministic poly-space simulation
- Languages that Capture Complexity Classes
- Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
- Nondeterministic Space is Closed under Complementation
- On relativizing auxiliary pushdown machines
- Limitations on Separating Nondeterministic Complexity Classes
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
- Alternation
- Relativizing Time, Space, and Time-Space
- A Hierarchy Theorem for Polynomial-Space Recognition
- Relativization of questions about log space computability
- Fast Parallel Matrix Inversion Algorithms
- Computational Complexity of Probabilistic Turing Machines
- Some Results on Tape-Bounded Turing Machines
- Classes of languages and linear-bounded automata
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A survey of space complexity
