callahan@cs.psu.edu (Paul B. Callahan) (01/12/90)
I'm looking for a paper which examines the parallel complexity of evaluating networks of comparator gates (the basic units of sorting networks). This is not the same as parallel sorting since arbitrary networks of comparators may not be sorters. I emphasize this, because I know there are many references on parallel sorting and I would like to save readers the trouble of telling me this. I have been given a vague reference to a paper which conjectures that this problem is in a complexity class harder than NC but that it is not P-complete. I have also been told that the same paper shows this problem to be equivalent to some forms of the stable marriage problem under log space reductions. However, the only information I've been given is that this work was done as part of a Stanford Ph.D. dissertation, and appeared at some conference. After a fairly extensive library search I was unable to find a paper fitting this description. For over a month I have been looking at a problem which I can reduce to lexicographically first maximal (*not* maximum) bipartite matching, which I was able to reduce to the problem of evaluating a comparator network. More recently, I was able to prove the converse of this reduction, showing these problems to be log space equivalent. Because the paper in question seems to be very close to what I am looking at, I am interested in seeing any of its related results. In particular, I would like to see the intuition behind the conjecture that this is a problem lying somewhere between NC and P-complete. Though I have had similar intuition, such a claim seems rather bold, and I would be interested in any convincing arguments. Thanks for any help. Paul Callahan callahan@crabcake.cs.jhu.edu callahan@psuvax1.cs.psu.edu
callahan@cs.psu.edu (Paul B. Callahan) (01/12/90)
In article <C0;5!x@cs.psu.edu> I wrote: >I'm looking for a paper which examines the parallel complexity of >evaluating networks of comparator gates (the basic units of sorting >networks). Thanks to all who responded. I've gotten the primary reference, namely "The complexity of circuit value and network stability" by Ernst W. Mayr and Ashok Subramanian, as well as a great deal of additional information. (not bad considering I posted shortly before lunch today). Paul Callahan callahan@crabcake.cs.jhu.edu callahan@psuvax1.cs.psu.edu