[36] Computing the minimum index: Modify the PRAM model as follows. We now have n processors P(1),...,P(n) and only one shared memory cell, c(1). Each processor knows one input bit. If several processors attempt to write into c(1) at the same time, then they must all write the same data; otherwise each write fails. This PRAM version requires

Ω(log n) time to find the smallest index i such that P(i) has input bit 1. Can you give two proofs, one using incompressibility arguments and the other not?

Comments. The original proof without using Kolmogorov complexity is due to F. Fich, P. Ragde, and A. Wigderson [SIAM J. Comput., 17:3(1988), 606–627].