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