Properties of complexity measures for PRAMs and WRAMs (Q580980)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Publication:580980 |
scientific article; zbMATH DE number 4018388
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Properties of complexity measures for PRAMs and WRAMs |
scientific article; zbMATH DE number 4018388 |
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
0 references
0 references
0.7950093746185303
0 references
0.7946318984031677
0 references
0.7941511273384094
0 references
