Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!mcsun!ukc!warwick!nott-cs!bhamcs!spsl
From: spsl@cs.bham.ac.uk (Steven Lam)
Newsgroups: comp.theory
Subject: Re: NP-completeness question
Keywords: NP-complete, NP-complete in strong sense, zero-one integer prog.
Message-ID: <1991Jun21.143830.4879@cs.bham.ac.uk>
Date: 21 Jun 91 14:38:30 GMT
References: <29269@uflorida.cis.ufl.EDU>
Sender: news@cs.bham.ac.uk
Organization: Birmingham University Computer Science
Lines: 14


More NP-complete problems,

I have developed a so-called "2 1/2-dimensional systolic array" which consists
of a two tightly coupled mesh arrays. By allowing each cell to communicate
with five neighbouring cells (i.e. four on the same layer and one on the 
adjacent layer), I have developed a reconfiguration scheme to recover a
defected array. Later on, I found that the connectivity constraint will have
to be relaxed further, i.e. diagonal connections between cells are allowed,
the resultant array gives a high percentage of fault tolerance. Now, the
question is whether it is a NP-complete problem to simulation this 
reconfigurable array? I will be gratefull to hear your comments. Thanks

Stephen