Complexity theory of parallel time and hardware

DOI10.1016/0890-5401(89)90009-6zbMath0666.68045OpenAlexW1998855954MaRDI QIDQ1116695

Patrick W. Dymond, Stephen A. Cook

Publication date: 1989

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90009-6

zbMATH Keywords

parallel computationparallel complexitycomplexity classescircuit depthcircuit widthaggregate hardwareaggregate time

Mathematics Subject Classification ID

Related Items (7)

Parallel pointer machines ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms. ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Cyclic Boolean circuits ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A tradeoff theorem for space and reversal
• A space efficient algorithm for the monotone planar circuit value problem
• Tree-size bounded alternation
• On uniform circuit complexity
• Towards a complexity theory of synchronous parallel computation
• The network complexity and the Turing machine complexity of finite functions
• Time bounded random access machines
• Relationships between nondeterministic and deterministic tape complexities
• Tape-reversal bounded Turing machine computations
• On similarity and duality of computation (I)
• Parallel Prefix Computation
• Storage Modification Machines
• Alternation
• A universal interconnection pattern for parallel computers
• Asymptotically tight bounds on time-space trade-offs in a pebble game
• On Relating Time and Space to Size and Depth
• Time Bounded Random Access Machines with Parallel Processing
• Parallelism in random access machines
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

This page was built for publication: Complexity theory of parallel time and hardware