Problems complete for deterministic logarithmic space
From MaRDI portal
Publication:3787477
Recommendations
Cited in
(52)- Decision problems for reversible and permutation automata
- Planar and grid graph reachability problems
- The complexity of circuit value and network stability
- Parameterized complexity of finding regular induced subgraphs
- Equivalence classes and conditional hardness in massively parallel computations
- Computing kernels in parallel: lower and upper bounds
- Pure Pointer Programs with Iteration
- Monomials, multilinearity and identity testing in simple read-restricted circuits
- Computation by interaction for space-bounded functional programming
- A compendium of problems complete for symmetric logarithmic space
- The arithmetic complexity of tensor contraction
- Complexity models for incremental computation
- Counting quantifiers, successor relations, and logarithmic space
- Parallel vertex colouring of interval graphs
- A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
- scientific article; zbMATH DE number 4062587 (Why is no real title available?)
- On the parallel complexity of linear groups
- The complexity of planarity testing
- Extensions to Barrington's M-program model
- The word problem for finitary automaton groups
- Completeness results for graph isomorphism.
- On the complexity of matrix rank and rigidity
- The expressiveness of a family of finite set languages
- Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space
- On the complexity of some problems on groups input as multiplication tables
- Reachability in \(K_{3,3}\)-free and \(K_5\)-free graphs is in unambiguous logspace
- Reversible space equals deterministic space
- Gradually intractable problems and nondeterministic log-space lower bounds
- The complexity of intersecting finite automata having few final states
- A new complete language for DSPACE(log n)
- On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology
- Dynamic complexity of expansion
- Low complexity algorithms in knot theory
- On the complexity of topological sorting
- Complexity of testing reachability in matroids
- Space-efficient graph kernelizations
- Distributed XML design
- Investigations concerning the structure of complete sets
- How to meet in anonymous network
- McNaughton families of languages.
- Oracle branching programs and Logspace versus \(P^*\)
- Isomorphism testing of read-once functions and polynomials
- On measures of space over real and complex numbers
- Approximation in (poly-) logarithmic space
- Finding regular subgraphs in both arbitrary and planar graphs
- Interleaved Group Products
- A note on logspace optimization
- On the complexity of inverse semigroup conjugacy
- Complexity and enumeration in models of genome rearrangement
- Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
- STACS 2004
- scientific article; zbMATH DE number 219246 (Why is no real title available?)
This page was built for publication: Problems complete for deterministic logarithmic space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787477)
