[26] A function f(x1,...,xn) is called invertible if for each i, argument xi can be computed from {x1,...,xn}−{xi} and f(x1,...,xn).

Use the PRAM model with q processors defined in this section. Show that it requires Ω(min{log(b(n)/ log q), log n}) time to compute any invertible function f(x1,...,xn), where l(xi) ≤ b(n), for all i, and log n =

o(b(n)).

Comments. Source: [M. Li and Y. Yesha, J. Assoc. Comp. Mach., 36:3(19 89), 671–680].