A theory of strict P-completeness

DOI10.1007/3-540-55210-3_171zbMath1493.68155OpenAlexW1498175479MaRDI QIDQ5096767

Anne Condon

Publication date: 18 August 2022

Published in: STACS 92 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55210-3_171

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Strict sequential P-completeness

Cites Work

• Unnamed Item
• Unnamed Item
• A complexity theory of efficient parallel algorithms
• Depth-first search is inherently sequential
• The problem of space invariance for sequential machines
• Parallel approximation algorithms for bin packing
• Time bounded random access machines
• A taxonomy of problems with fast parallel algorithms
• An Efficient Parallel Biconnectivity Algorithm
• On the sequential nature of unification
• The Complexity of Markov Decision Processes
• New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for P
• Parallelism in random access machines

This page was built for publication: A theory of strict P-completeness