Symmetric space-bounded computation
From MaRDI portal
Publication:1167537
DOI10.1016/0304-3975(82)90058-5zbMath0491.68045OpenAlexW2039302045WikidataQ55891641 ScholiaQ55891641MaRDI QIDQ1167537
Harry R. Lewis, Christos H. Papadimitriou
Publication date: 1982
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(82)90058-5
stack automatadeterministic and nondeterministic classesspace complexity classesspace symmetric classesspace-time complexity classessymmetric complexity space classsymmetric Turing machineword problem for balanced Thue systems
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Word problems, etc. in computability and recursion theory (03D40) Thue and Post systems, etc. (03D03)
Related Items
Equivalence classes and conditional hardness in massively parallel computations, Randomized and Symmetric Catalytic Computation, An unambiguous class possessing a complete set, The complexity of pure literal elimination, FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY, Reversibility in space-bounded computation, Inequalities for the number of walks in graphs, On approximating the eigenvalues of stochastic matrices in probabilistic logspace, Space-efficient algorithms for reachability in directed geometric graphs, Reconfiguration in bounded bandwidth and tree-depth, Matrix power inequalities and the number of walks in graphs, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, Completeness results for graph isomorphism., Unnamed Item, Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree, A combinatorial algorithm for Horn programs, Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem, Absorbing random walks and the NAE2SAT problem, Complete problems for symmetric logspace involving free groups, Towards efficient universal planning: A randomized approach, Expected parallel time and sequential space complexity of graph and digraph problems, Knapsack problems for NL, Reversible simulation of space-bounded computations, Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space, Capturing complexity classes by fragments of second-order logic, CNF and DNF succinct graph encodings, Methods for proving completeness via logical reductions, Using the Hamiltonian path operator to capture NP, Cyclic Extensions of Order Varieties, On the reducibility of sets inside NP to sets with low information content, Finite graph automata for linear and boundary graph languages, Quantum simulations of classical random walks and undirected graph connectivity, Computational complexity of some problems involving congruences on algebras, On memoryless provers and insincere verifiers, Complexity of path discovery game problems, Reversible space equals deterministic space, Space complexity of reachability testing in labelled graphs, \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\), Feasibility checking in Horn constraint systems through a reduction based approach, Complexity of the word problem for commutative semigroups of fixed dimension, Space-bounded hierarchies and probabilistic computations, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The directed subgraph homeomorphism problem
- Space-bounded reducibility among combinatorial problems
- Translational lemmas, polynomial time, and \((\log n)^j\)-space
- Nonerasing stack automata
- Relationships between nondeterministic and deterministic tape complexities
- A Polynomial Solution to the Undirected Two Paths Problem
- New problems complete for nondeterministic log space
- Computational Complexity of Probabilistic Turing Machines
- Recursive Unsolvability of a problem of Thue
- The subgraph homeomorphism problem
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- A Note Concerning Nondeterministic Tape Complexities
