Properties of complexity measures for PRAMs and WRAMs

DOI10.1016/0304-3975(86)90083-6MaRDI QIDQ580980zbMATHOpenAlexFDO

Authors 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

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Publication:4728250
• Publication:3031933
• The critical complexity of all (monotone) boolean functions and monotone graph properties
• Time Complexity of Boolean Functions on CREW PRAM<scp>s</scp>
• CREW PRAM<scp>s</scp> and Decision Trees

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3825713 (Why is no real title available?)
• scientific article; zbMATH DE number 3829252 (Why is no real title available?)
• scientific article; zbMATH DE number 4041254 (Why is no real title available?)
• scientific article; zbMATH DE number 3632542 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• On recognizing graph properties from adjacency matrices
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
• The critical complexity of all (monotone) boolean functions and monotone graph properties
• The critical complexity of graph properties
• Trade-Offs between Depth and Width in Parallel Computation
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cited in

(9)

• The nonapproximability of OBDD minimization
• scientific article; zbMATH DE number 4003532 (Why is no real title available?)
• Parallel information-based complexity
• scientific article; zbMATH DE number 4130025 (Why is no real title available?)
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• The complexity of symmetric functions in bounded-depth circuits
• Gossiping and broadcasting versus computing functions in networks.
• Quantum certificate complexity
• Composition limits and separating examples for some Boolean function complexity measures

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

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