Properties of complexity measures for PRAMs and WRAMs (Q580980): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q1168287 |
||
| Property / author | |||
| Property / author: Ute Schuerfeld / rank | |||
Revision as of 13:15, 22 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Properties of complexity measures for PRAMs and WRAMs |
scientific article |
Statements
Properties of complexity measures for PRAMs and WRAMs (English)
0 references
1986
0 references
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.
0 references
computation of Boolean functions
0 references
parallel computers with shared memory
0 references
PRAMs
0 references
WRAMs
0 references
complexity measures for parallel computers
0 references
complexity measures for Boolean functions
0 references
