allender@CS.RUTGERS.EDU (Eric Allender) (03/02/90)
Many thanks to those of you who responded with information concerning EREW PRAMs and NC^1. Thanks especially to Paul Beame, Joan Lucas, and Vijaya Ramachandran, who pointed out that any language in DLOG (deterministic log space) can be recognized by an EREW PRAM in log time. Since NC^1 is contained in DLOG, and many people suspect that the containment is proper, it seems unlikely that NC^1 corresponds to log time on an EREW PRAM. (Sketch of the simulation: use the "Euler Tour" method. The configuration graph of a DLOG machine yields two trees: one rooted at the ACCEPT state, and one rooted at the REJECT state. Assign two processors to each edge in this graph -- one processor for the "forward" direction, and one for the "backward" direction. The processors can easily compute their predecessors and successors in an Euler tour of their tree, starting at the root. Now use pointer jumping to find which tree the start configuration is in.) OPEN QUESTION: To whom can this be attributed? Thanks also to Peter Clote and Ruediger Reischuk, for bringing to my attention a paper by Klaus-Joern Lange in the upcoming Structure conference, in which CREW-PRAM time is characterized in terms of "unambiguous" circuits. - Eric Allender