Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!gatech!hubcap!"Farid
From: alizadeh@cs.umn.edu (Farid Alizadeh)
Newsgroups: comp.parallel
Subject: hypercubes and the class NC
Keywords: Parallel algorithms, class NC, hypercubes, polylog algorithms
Message-ID: <6295@hubcap.clemson.edu>
Date: 21 Aug 89 12:14:40 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 29
Approved: parallel@hubcap.clemson.edu

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