allender@cs.rutgers.EDU (Eric Allender) (02/28/90)
Can anyone clarify the status of the following "folk theorem": NC^1 = log time on an EREW PRAM. In particular * Is it correct? * If so, where is it proved? * Is this question discussed anywhere? Note that this is NOT the definition of NC^1 (although one occasionally sees a paper in which ANY log-time algorithm -- or at least log time on an EREW PRAM -- is called an NC^1 algorithm). Instead, NC^1 is usually defined in terms of (uniform) families of log-depth fan-in 2 circuits of AND and OR gates, or in terms of Boolean formulae, or in terms of alternating Turing machines, or in terms of Bounded-Width Branching Programs, or in any of many other equivalent formulations. Note that various other models of PRAM are known to correspond exactly to complexity classes. For example: log time on a CRCW PRAM = AC^1 [Stockmeyer and Vishkin] log time on a CROW PRAM = log(DCFL) [Dymond and Ruzzo] (This last result requires some explanation. CROW means "Concurrent Read Owner Write"; the "owner write" restriction means that a processor can only write into memory locations that it "owns". Thus this gives a policy for enforcing the "exclusive write" restriction. The class of sets reducible to determistic context-free languages is log(DCFL).) It is easy to define something like an "Owner Read Owner Write" PRAM that corresponds exactly to NC^1, but such a model seems quite restrictive. Thus it would be nice if NC^1 really does correspond to EREW PRAMs. Note that it is not a-priori obvious that a CROW PRAM can simulate an EREW PRAM (although log(DCFL) clearly contains NC^1). Any pointers will be appreciated, -- Eric Allender