Techniques for separating space complexity classes
From MaRDI portal
Publication:1235979
DOI10.1016/S0022-0000(77)80041-XzbMath0352.68062MaRDI QIDQ1235979
Publication date: 1977
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
Related Items
Multihead two-way probabilistic finite automata, Multihead two-way probabilistic finite automata, A space-hierarchy result on two-dimensional alternating Turing machines with only universal states, On the structure of one-tape nondeterministic Turing machine time hierarchy, Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs, Finite automata and unary languages, Hierarchies of one-way multihead automata languages, Cyclic automata, On the complexity of deciding fair termination of probabilistic concurrent finite-state programs, Hierarchy of complexity of computation of partial functions with values 0 and 1, On time-space classes and their relation to the theory of real addition, On eliminating nondeterminism from Turing machines which use less than logarithm worktape space, A survey of space complexity, A multiparameter analysis of domino tiling with an application to concurrent systems, Relating refined space complexity classes, P-RAM vs. RP-RAM, Communicating processes, scheduling, and the complexity of nontermination, Gradually intractable problems and nondeterministic log-space lower bounds, Unnamed Item, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Space bounds for processing contentless inputs
- Hierarchies of Turing machines with restricted tape alphabet size
- Relating refined space complexity classes
- A hierarchy for nondeterministic time complexity
- Relationships between nondeterministic and deterministic tape complexities
- Tape-bounded Turing acceptors and principal AFLs
- On two-way multihead automata
- A class of universal linear bounded automata
- Classes of Predictably Computable Functions
- A Hierarchy Theorem for Polynomial-Space Recognition
- Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
- Separating Nondeterministic Time Complexity Classes
- Infinite exponent partition relations and well-ordered choice
- Some Results on Tape-Bounded Turing Machines
- The Operator Gap
- A Note Concerning Nondeterministic Tape Complexities
- On Languages Accepted in Polynomial Time
- Computational Complexity and the Existence of Complexity Gaps