A theory of strict P-completeness
From MaRDI portal
Publication:5096767
DOI10.1007/3-540-55210-3_171zbMath1493.68155MaRDI QIDQ5096767
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
68W10: Parallel algorithms in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
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