It was shown some years ago that the computation time for many important
Boolean functions of n arguments on concurrent-read exclusive-write
parallel random-access machines
(CREW PRAMs) of unlimited size is at least f(n) = 0.72 log n.
On the other hand, it is known that every Boolean function of n
arguments can be computed in f(n)+1 steps on a CREW PRAM with
n* 2^{n-1} processors and memory cells.
In the case of the OR of n bits, n processors and cells are sufficient.

In this paper it is shown that for many important functions
there are CREW PRAM algorithms that almost meet the lower bound in
that they take f(n) + o(log n) steps,
but use only a small number of processors and memory cells (in most cases, n).
In addition, the cells only have to store binary words of bounded length
(in most cases, length~1). We call such algorithms ``feasible''.

The functions concerned include: the PARITY function and, more generally,
all symmetric functions; a large class of Boolean formulas; some functions over
non-Boolean domains {0,\ldots ,k-1} for small k, in particular parallel
prefix sums; addition of n-bit-numbers; sorting n/l binary numbers of length l.

Further, it is shown that Boolean circuits with fan-in 2, depth d, and
size s can be evaluated by CREW PRAMs with fewer than s processors
in f(2^d)+o(d) = 0.72d+ o(d) steps.

For the exclusive-read exclusive-write model (EREW PRAM) a feasible algorithm
is described that computes PARITY of n bits in 0.86 log n steps.