[Gllug] Best option for a lot of compute power

[Pete Ryland]

On Mon, Jun 07, 2004 at 08:54:29PM +0100, John Winters wrote:
> On Mon, 2004-06-07 at 17:17, Pete Ryland wrote:
> > On Mon, Jun 07, 2004 at 05:12:07PM +0100, Bernard Peek wrote:
> > > In message <20040607143848.GE6325 at pigeonhold.com>, Doug Winter <doug at pigeonhold.com> writes
> > > >Sounds NP-Complete to me, so presumably could involve an exhaustive
> > > >search, which could take a very very long time otherwise?
> > > 
> > > I've heard it quoted as an example of a problem that can't currently be 
> > > solved by anything except a brute-force approach.
> > 
> > In the general case it is indeed NP-complete, but generally in
> > practice this is not the case.
> 
> Can you provide any background to this claim?  It would be nice to find
> a way of cutting out all the number crunching.

The problem can be reduced considerably if you start adding arbitrary rules.
For example, all first formers must take English (I hope), so you could
stipulate that they all take it at the same time (if you have enough English
teachers).  Keep adding constraints like this and the problem will almost
solve itself.  And you'll also end up with a much simpler time-table.

Pete
-- 
Gllug mailing list  -  Gllug at gllug.org.uk
http://lists.gllug.org.uk/mailman/listinfo/gllug