[Gllug] Best option for a lot of compute power

[Pete Ryland]

On Tue, Jun 08, 2004 at 05:06:07PM +0100, John Winters wrote:
> On Tue, 2004-06-08 at 13:13, Pete Ryland wrote:
> > On Mon, Jun 07, 2004 at 08:54:29PM +0100, John Winters wrote:
> > > On Mon, 2004-06-07 at 17:17, Pete Ryland wrote:
> [snip]
> > > > 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.
> 
> Unfortunately the arbitrary "extra" rules you suggest are already the
> norm.  Everyone takes English and Maths and this has to be scheduled for
> a whole year at the same time (because the streaming for English, Maths
> and other things is not the same).  Your "simpler" version is therefore
> the current state of affairs, and no simpler.

I suppose it's still NP-complete over this smaller space, but it's a
*hugely* smaller space than the general case - that's basically all I was
saying.

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