Properties of complexity measures for PRAMs and WRAMs
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.
complexity measures for parallel computers
complexity measures for Boolean functions
scientific article; zbMATH DE number 4018388
scientific article