A theory of strict P-completeness

DOI10.1007/BF01206637zbMath0812.68072MaRDI QIDQ1337145

Anne Condon

Publication date: 30 October 1994

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

parallel machinesP-completenesspolynomial speedup

Mathematics Subject Classification ID

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

Related Items

Strict sequential P-completeness ⋮ Parallel Computation Using Active Self-assembly ⋮ Parallel computation using active self-assembly ⋮ The Parallel Complexity of Coloring Games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A complexity theory of efficient parallel algorithms
• Sorting in \(c \log n\) parallel steps
• Depth-first search is inherently sequential
• The problem of space invariance for sequential machines
• Parallel approximation algorithms for bin packing
• A model classifying algorithms as inherently sequential with applications to graph searching
• Time bounded random access machines
• A taxonomy of problems with fast parallel algorithms
• On the sequential nature of unification
• The Complexity of Markov Decision Processes
• Parallel Prefix Computation
• New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for P
• Parallelism in random access machines
• Flow diagrams, turing machines and languages with only two formation rules