A compendium of problems complete for symmetric logarithmic space

DOI10.1007/PL00001603MaRDI QIDQ5930152zbMATH OpenWikidataFDO

Authors Carme Àlvarez, Raymond Greenlaw

Publication date 17 April 2001

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/PL00001603

zbMATH Keywords

symmetric logarithmic space

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 1101593
• Problems complete for deterministic logarithmic space
• scientific article; zbMATH DE number 1101597
• Complete problems for symmetric logspace involving free groups
• A very hard log-space counting class

Cited in

(14)

• The complexity of satisfiability problems: Refining Schaefer's theorem
• Equivalence classes and conditional hardness in massively parallel computations
• On the complexity of matrix rank and rigidity
• On approximating the eigenvalues of stochastic matrices in probabilistic logspace
• Complement, complexity, and symmetric representation
• scientific article; zbMATH DE number 1332655 (Why is no real title available?)
• Probabilistic logarithmic-space algorithms for Laplacian solvers
• Applications of the quantum algorithm for st-connectivity
• Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
• Cyclic extensions of order varieties
• A faster algorithm for determining the linear feasibility of systems of BTVPI constraints
• The complexity of bidirected reachability in valence systems
• Logical expressibility of syntactic NL for complementarity and maximization
• Problems complete for \(\oplus L\)

This page was built for publication: A compendium of problems complete for symmetric logarithmic space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5930152)