Parallel searching of multidimensional cubes (Q685702)

Let \((P,\leq)\) be a finite partially ordered set and let \(f:P \to R\) be an order-preserving, injective, real-valued function. The search problem associated with \(P\) is: Given a real number \(x\), determine if there exists \(p \in P\) such that \(f(p) = x\), and find such a \(p\) if it exists. An elementary step is the evaluation of \(f\) at some \(p \in P\). The complexity \(c(P)\) of the search problem is the minimum, over all algorithms for the problem, of the maximum number of steps taken by the algorithm. When \(k\) processors are used, the complexity is denoted by \(c_ k (P)\). In this paper the authors consider the search problem when \(P\) is a product of several chains of the same length. \(Q_{nd}\) denotes the \(d\)- dimensional cube of side length \(n\), and we write \(W(n,d,k)\) for \(c_ k (Q_{nd})\). The authors prove that \(W(n,d,n^{d-1}) = \Theta (\log \log n)\) and that, moreover, any randomized algorithm using \(n^{d-1}\) processors for searching \(Q_{nd}\) takes time \(\Omega (\log \log n)\).