A theory of strict P-completeness

DOI10.1007/BF01206637MaRDI QIDQ1337145zbMATH OpenFDO

Authors Anne Condon

Publication date 30 October 1994

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01206637

zbMATH Keywords

P-completenessparallel machinespolynomial speedup

Mathematics Subject Classification ID

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

Recommendations

• A theory of strict P-completeness
• Strict sequential P-completeness
• scientific article; zbMATH DE number 175748
• Strong Completeness of a Pure Free Logic
• Typed Lambda Calculi and Applications
• scientific article; zbMATH DE number 1868521
• On strictly arithmetical completeness in logics of programs
• Theory of completeness for logical spaces
• Completeness theory for propositional logics
• Completeness theorems for some intermediate predicate calculi

Cites work

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

Cited in

(9)

• Parallel computation using active self-assembly
• The Parallel Complexity of Coloring Games
• Strong Completeness of a Pure Free Logic
• scientific article; zbMATH DE number 3988236 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• Strict sequential P-completeness
• A theory of strict P-completeness
• Parallel Computation Using Active Self-assembly
• On strict strong constructibility with a compass alone

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1337145)