CREW-PRAM's are a powerful model of parallel computers. Lower bounds for this model are rather general. \textit{S. A. Cook}, \textit{C. Dwork} and \textit{R. Reischuk} [SIAM J. Comput. 15, 87-97 (1986)] proved that the CREW-PRAM complexity of Boolean functions is bounded by \(\log_ b(f)\), where \(b\approx 4.79\) and c(f) is the critical complexity of f. This lower bound is often even tight. For a class of functions F the critical complexity c(F), the minimum of all c(f) where \(f\in F\), is the best general lower bound on the critical complexity of all \(f\in F\). We determine the critical complexity of the set of all nondegenerate Boolean functions and all monotone nondegenerate Boolean functions up to a small additive term. And we compute exactly the critical complexity of the class of all monotone graph properties, proving partially a conjecture of \textit{G. Turán} [Inf. Process. Lett. 18, 151-153 (1984; Zbl 0542.68026)].