Alexander Viro <viro@math.psu.edu>:
> Assertion: you can split the set of variables into disjoint union of
> small subsets X, Y_1,...,Y_m such that each constraint is concerned
> only with variables from X and at most one of Y_i.
>
> IOW, there is a small "core" and for fixed values of core variables
> constraints fall into groups, each dealing with its own _small_
> set of variables.
>
> If that assertion is true the complexity is nowhere near 3^N.
>
> Eric, you probably have the most accurate information about the
> existing constraints. Care to verify the assertion above? I'm
> serious - the set of constraints is very far from generic and
> if nothing else, such preprocessing (splitting variables into
> core and peripherial groups) can make life easier in other
> parts of the thing.
You're almost right. If you counted only explicit constraints,
created by require statements, you get a bunch of cliques that
aren't that large.
Unfortunately....there are a huge bunch of implicit constraints
created by dependency relationships in the menu tree. For example,
all SCSI cards are dependents of the SCSI symbol. Set SCSI to N
and all the card symbols get turned off; set any card symbol to Y or M
and the value of SCSI goes to Y or M correspondingly.
So the way it actually works (I think; I've have to write code to do a
topological analysis to be sure) out is that there's sort of a light
dust of atoms (BSD quota is one of them) surrounding one huge gnarly
menu-tree-shaped clique.
-- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>Strict gun laws are about as effective as strict drug laws...It pains me to say this, but the NRA seems to be right: The cities and states that have the toughest gun laws have the most murder and mayhem. -- Mike Royko, Chicago Tribune - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Mon May 07 2001 - 21:00:16 EST