`"Eric S. Raymond" wrote:> > 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.> Are the dependencies for each disjoint union kept hierarchically?  Suchas:setting C = 'y' requires B = 'y'setting B = 'y' requires A = 'y' etc.If so, given the above ruleset involving symbols A, B and C, and giventhat such a ruleset is violated for some reason (you don't even carewhy), use the following approach:set C to 'n' -> are we ok?set B to 'n' -> are we ok?set A to 'n' -> are we ok?Inform the user of each change.  In a massively broken configuration youcould end up with a lot of stuff set to 'n' ultimately, but I think thatthis generally would just end up shutting off troublesome configurationsettings, and requiring that the user then reset them manually.In my example above I've idealized your idealized world of tristatesinto a world of bistates.  How do you like that :-)Instead of trying all possible combinations, instead for 2000 symbolsyou only need (worst case) to check 2000 - each iteration you will havechanged one setting from y to n, so the most you can do is 2000 checks.David-- David Mansfield                                           (718) 963-2020david@ultramaster.comUltramaster Group, LLC                               www.ultramaster.com-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/`