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 classesgraph problemslogarithmic spacelogarithmic timepolynomial number of processorspolynomial timeprobabilistic 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)

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

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)