Alexander Viro <[EMAIL PROTECTED]>:
> 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 [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
