Symmetric space-bounded computation
From MaRDI portal
Cites work
- A Note Concerning Nondeterministic Tape Complexities
- A Polynomial Solution to the Undirected Two Paths Problem
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Computational Complexity of Probabilistic Turing Machines
- scientific article; zbMATH DE number 3727583 (Why is no real title available?)
- scientific article; zbMATH DE number 3568660 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- scientific article; zbMATH DE number 3407150 (Why is no real title available?)
- New problems complete for nondeterministic log space
- Nonerasing stack automata
- Recursive unsolvability of a problem of Thue
- Relationships between nondeterministic and deterministic tape complexities
- Space-bounded reducibility among combinatorial problems
- The directed subgraph homeomorphism problem
- The subgraph homeomorphism problem
- Translational lemmas, polynomial time, and \((\log n)^j\)-space
Cited in
(45)- Space-bounded hierarchies and probabilistic computations
- Complete problems for symmetric logspace involving free groups
- Expected parallel time and sequential space complexity of graph and digraph problems
- Capturing complexity classes by fragments of second-order logic
- Using the Hamiltonian path operator to capture NP
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- Completeness results for graph isomorphism.
- Complexity of path discovery game problems
- Reversible space equals deterministic space
- Reconfiguration in bounded bandwidth and tree-depth
- On the reducibility of sets inside NP to sets with low information content
- Finite graph automata for linear and boundary graph languages
- Towards efficient universal planning: A randomized approach
- Equivalence classes and conditional hardness in massively parallel computations
- Space complexity of reachability testing in labelled graphs
- Feasibility checking in Horn constraint systems through a reduction based approach
- On approximating the eigenvalues of stochastic matrices in probabilistic logspace
- A combinatorial algorithm for Horn programs
- Reversibility in space-bounded computation
- On memoryless provers and insincere verifiers
- Inequalities for the number of walks in graphs
- Matrix power inequalities and the number of walks in graphs
- Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
- \(n\)-permutability and linear Datalog implies symmetric Datalog
- FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY
- Probabilistic logarithmic-space algorithms for Laplacian solvers
- Randomized and Symmetric Catalytic Computation
- An unambiguous class possessing a complete set
- CNF and DNF succinct graph encodings
- Absorbing random walks and the NAE2SAT problem
- Cyclic extensions of order varieties
- Quantum simulations of classical random walks and undirected graph connectivity
- Computational complexity of some problems involving congruences on algebras
- Space-efficient algorithms for reachability in directed geometric graphs
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- Knapsack problems for NL
- Reversible simulation of space-bounded computations
- Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
- Methods for proving completeness via logical reductions
- Bisimilarity in fresh-register automata
- Unambiguous, randomized, and symmetric catalytic computation
- Parameterized complexities of dominating and independent set reconfiguration
- Complexity of the word problem for commutative semigroups of fixed dimension
- The complexity of pure literal elimination
- Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree
This page was built for publication: Symmetric space-bounded computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1167537)
