Symmetric Complementation

DOI10.1145/62.322436MaRDI QIDQ3769977zbMATH OpenOpenAlexFDO

Authors J. Reif

Publication date 1984

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/62.322436

zbMATH Keywords

complexity classeslogarithmic spacepolynomial timegraph problemslogarithmic timepolynomial number of processorsprobabilistic parallelism algorithmsprobabilistic sequential algorithmssymmetric complementing games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of game theory (91A80)

Recommendations

• scientific article; zbMATH DE number 1241622
• Symmetric synthesis
• Symmetric operations
• Simultaneous symmetrization
• Complement, complexity, and symmetric representation
• Symmetric complete intersections
• Symmetric Reductions
• Symmetric variation

Cited in

(16)

• Approximation in (poly-) logarithmic space
• Absorbing random walks and the NAE2SAT problem
• Complete problems for symmetric logspace involving free groups
• Optimal parallel randomized algorithms for sparse addition and identification
• Complement, complexity, and symmetric representation
• Frameworks for designing in-place graph algorithms
• A framework for in-place graph algorithms
• Depth-first search is inherently sequential
• Sublinear-space approximation algorithms for Max \(r\)-SAT
• The complexity of planarity testing
• Approximation in (Poly-) Logarithmic Space
• Symmetric variation
• Planarity testing in parallel
• On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls
• Expected parallel time and sequential space complexity of graph and digraph problems
• Planarity testing revisited

This page was built for publication: Symmetric Complementation

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