Properties of complexity measures for PRAMs and WRAMs

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

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)

Review text

The computation of Boolean functions by parallel computers with shared memory (PRAMs and WRAMs) is considered. In particular, complexity measures for parallel computers like critical and sensitive complexity are compared with other complexity measures for Boolean functions like branching program depth and length of prime implicants and clauses. The relations between these complexity measures and their asymptotic behaviour are investigated for the classes of Boolean functions, monotone functions and symmetric functions.

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

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)