Properties of complexity measures for PRAMs and WRAMs

DOI10.1016/0304-3975(86)90083-6zbMath0626.68040OpenAlexW2064007242MaRDI QIDQ580980

Siegfried Bublitz, Ingo Wegener, Ute Schuerfeld

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90083-6

zbMATH Keywords

complexity measures for Boolean functionscomplexity measures for parallel computerscomputation of Boolean functionsparallel computers with shared memoryPRAMsWRAMs

Mathematics Subject Classification ID

Related Items (7)

Exact lower time bounds for computing Boolean functions on CREW PRAMs ⋮ The complexity of symmetric functions in bounded-depth circuits ⋮ Composition limits and separating examples for some Boolean function complexity measures ⋮ Gossiping and broadcasting versus computing functions in networks. ⋮ Parallel information-based complexity ⋮ Quantum certificate complexity ⋮ The nonapproximability of OBDD minimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The critical complexity of graph properties
• On recognizing graph properties from adjacency matrices
• Trade-Offs between Depth and Width in Parallel Computation
• The critical complexity of all (monotone) boolean functions and monotone graph properties
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions

This page was built for publication: Properties of complexity measures for PRAMs and WRAMs