Properties of complexity measures for PRAMs and WRAMs

AbstractThe 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