Complexity theory of parallel time and hardware
type: Item
instance of: scholarly article
title: Complexity theory of parallel time and hardware
zbMATH Open document ID: 0666.68045
DOI: 10.1016/0890-5401(89)90009-6
author: P. Dymond
author: Stephen Cook
published in: Information and Computation
publication date: 1989-01-01T00:00:00Z
review text: The parallel resources time and hardware and the complexity classes defined by them are studied using the aggregate model. The equivalence of complexity classes defind by sequential space and uniform aggregate hardware is established. Aggregate time is related to (bounded fanin) circuit depth and, similarly, aggregate hardware is relaed to circuit width. Interelationships between aggregate time and hardware follow as corollaries. Aggregate time is related to the sequential resource reversal. Simultaneous relationships from aggregate hardware and time to sequential space and reversal are shown (and conversely), and these are used as evidence for an ``extended parallel computation thesis''. These simultaneous relationships provide new characterizations for the simultaneous parallel complexity class NC and for the complementary class SC. The evaluation of monotone planar circuits is shown to be in NC, in fact in LOGCFL.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 4090799
zbMATH Keywords: complexity classes
zbMATH Keywords: circuit depth
zbMATH Keywords: aggregate hardware
zbMATH Keywords: circuit width
zbMATH Keywords: aggregate time
zbMATH Keywords: parallel computation
zbMATH Keywords: parallel complexity
MaRDI profile type: Publication
full work available at URL: 0890-5401(89)90009-6
OpenAlex ID: W1998855954
cites work: Q5527003
cites work: On Relating Time and Space to Size and Depth
cites work: Alternation
cites work: Time bounded random access machines
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: Towards a complexity theory of synchronous parallel computation
cites work: Q3730022
cites work: Parallelism in random access machines
cites work: A universal interconnection pattern for parallel computers
cites work: A space efficient algorithm for the monotone planar circuit value problem
cites work: Q3862379
cites work: Tape-reversal bounded Turing machine computations
cites work: On similarity and duality of computation (I)
cites work: A tradeoff theorem for space and reversal
cites work: Parallel Prefix Computation
cites work: Asymptotically tight bounds on time-space trade-offs in a pebble game
cites work: Q5341755
cites work: Q5608026
cites work: Tree-size bounded alternation
cites work: On uniform circuit complexity
cites work: Time Bounded Random Access Machines with Parallel Processing
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Storage Modification Machines
cites work: The network complexity and the Turing machine complexity of finite functions
description: scientific article; zbMATH DE number 4090799