alizadeh@cs.umn.edu (Farid Alizadeh) (08/21/89)
Here is a theoretical question concerning parallel complexity classes.
It seems to me that the hypercube model of computation is weaker than
the PRAM model (although I doubt there is any proof of this as there are
very few proved items in complexity theory.) Intuitively, in a PRAM model
each processor (P.E.) can talk to another directly via random access memory,
whereas in hypercube each P.E. can communicate only to log(n) other P.E.'s
directly. (Assuming there are n P.E.'s available altogether.) Nevertheless it
seems that just about any problem for which there is a polylogarithmic algorithm
using polynomial number of processors on a PRAM, has a comparable algorithm
(polylog time, polynomial # of P.E.'s) on a hypercube. (In the literature the
class of problems for which there exists a polylog algorithm using polynomial
number of processors on a PRAM is called the class NC. Let us temporarily call
the class of problems for which there is a polylog time/polynomial P.E.
algorithm on a hypercube LOG-NCUBE.) Examples of problems (functions) known to
be in both NC and LOG-NCUBE are: sorting, adding/multiplying n numbers, matrix
multiplication, determinant, matrix inversion, shortest paths in graphs,
transitive closure in graphs, and many, many more.
Clearly LOG-NCUBE is a subset of NC. I bet it is a
hard (probably open) problem to determine if NC is a subset of LOG-NCUBE. My
question is: Is there any natural or artificially constructed function known
to belong to NC but not known to be in LOG-NCUBE? Has somebody developed the
concept of NC-complete problem with respect to, say LOG-NCUBE reductions?
I would appreciate any reference or examples on this.
Farid Alizadeh
Computer Science Dept.
University of Minnesota
alizadeh@umn-cs.cs.umn.edu
alizadeh@umn-cs.CS.UMN.EDU (Farid Alizadeh) (08/24/89)
In article <6295@hubcap.clemson.edu> alizadeh@cs.umn.edu I write: >... Let us temporarily call >the class of problems for which there is a polylog time/polynomial P.E. >algorithm on a hypercube LOG-NCUBE... >... My >question is: Is there any natural or artificially constructed function known >to belong to NC but not known to be in LOG-NCUBE? Has somebody developed the >concept of NC-complete problem with respect to, say LOG-NCUBE reductions? >I would appreciate any reference or examples on this. I guess I should have done more reading. A hypercube can simulate a PRAM with a loss of O(logn) time and with no need for more additional P.E's. Furthermore, other models of computation can simulate PRAMs. Among them are cube-connected- cycles, pyramids, perfect-shuffles, etc. On the other hand, some models of computation are provably weaker, for instance, 2-D meshes (sorting requires at least Omega(sqrt(n)) time.) Thanks for all of you who enlightened me on this subject. Farid Alizadeh Computer Science Dept. U. of Minn. alizadeh@umn-cs.cs.umn.edu