Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!ncar!gatech!hubcap!alizadeh
From: alizadeh@umn-cs.CS.UMN.EDU (Farid Alizadeh)
Newsgroups: comp.parallel
Subject: Re: hypercubes and the class NC
Keywords: Parallel algorithms, class NC, hypercubes, polylog algorithms
Message-ID: <6316@hubcap.clemson.edu>
Date: 23 Aug 89 18:51:47 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 22
Approved: parallel@hubcap.clemson.edu

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