A theory of strict P-completeness
type: Item
instance of: scholarly article
title: A theory of strict P-completeness
zbMATH Open document ID: 0812.68072
DOI: 10.1007/BF01206637
author: Anne Condon
published in: Computational Complexity
publication date: 1994-10-30T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W10
zbMATH DE Number: 679597
zbMATH Keywords: P-completeness
zbMATH Keywords: polynomial speedup
zbMATH Keywords: parallel machines
MaRDI profile type: Publication
cites work: Sorting in \(c \log n\) parallel steps
cites work: Parallel approximation algorithms for bin packing
cites work: Flow diagrams, turing machines and languages with only two formation rules
cites work: Time bounded random access machines
cites work: A taxonomy of problems with fast parallel algorithms
cites work: On the sequential nature of unification
cites work: Parallelism in random access machines
cites work: Q4128417
cites work: A model classifying algorithms as inherently sequential with applications to graph searching
cites work: Q3266141
cites work: Q4385522
cites work: A complexity theory of efficient parallel algorithms
cites work: Parallel Prefix Computation
cites work: The Complexity of Markov Decision Processes
cites work: Depth-first search is inherently sequential
cites work: New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for P
cites work: The problem of space invariance for sequential machines
Recommended article: A theory of strict P-completeness
Recommended article: Strict sequential P-completeness
Recommended article: Q4034802
Recommended article: Strong Completeness of a Pure Free Logic
Recommended article: Typed Lambda Calculi and Applications
Recommended article: Q4793765
Recommended article: On strictly arithmetical completeness in logics of programs
Recommended article: Theory of completeness for logical spaces
Recommended article: Completeness theory for propositional logics
Recommended article: Completeness theorems for some intermediate predicate calculi
description: scientific article; zbMATH DE number 679597