The critical complexity of all (monotone) boolean functions and monotone graph properties

DOI10.1016/S0019-9958(85)80036-XzbMath0588.68024MaRDI QIDQ3716300

Ingo Wegener

Publication date: 1985

Published in: Information and Control (Search for Journal in Brave)

zbMATH Keywords

parallel computationconcurrencyparallel random access machinescritical complexityCREW- PRAM complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (6)

A note on the size of minimal covers ⋮ On the generalized dimension and codimension of simple games ⋮ Properties of complexity measures for PRAMs and WRAMs ⋮ Sensitivities and block sensitivities of elementary symmetric Boolean functions ⋮ Cubic Formula Size Lower Bounds Based on Compositions with Majority ⋮ Complexity measures and decision tree complexity: a survey.

This page was built for publication: The critical complexity of all (monotone) boolean functions and monotone graph properties