Lower bounds for recognizing small cliques on CRCW PRAM’s

We show that any CRCW PRAM which recognizes k-cliques in n-node graphs in time T re-quires at least nn(k’r2) processors independent of its memory size. As a corollary we obtain essentially the same trade-off for unbounded fan-in circuits. We also demonstrate a similar but weaker trade-off for the memory size of CRCW PRAM’s solving this problem independent of the number of processors. These bounds also answer an open question posed in 1131, i.e., they show that constant-depth circuits for recognizing k-cliques in n-node graphs require size neck). 1