Symmetric Complementation

DOI10.1145/62.322436zbMath0632.68062OpenAlexW2293273465MaRDI QIDQ3769977

John H. 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

polynomial timecomplexity classeslogarithmic spacegraph problemslogarithmic timepolynomial number of processorsprobabilistic parallelism algorithmsprobabilistic sequential algorithmssymmetric complementing games

Mathematics Subject Classification ID

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

Related Items (14)

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

This page was built for publication: Symmetric Complementation