Warren wrote, in part: > > I believe the brute force approach of just solving the > NP-hard redistricting problem > perfectly, is not feasible. There are probably ten-thousands > of census blocks > and exponential runtimes with that much input just do not > happen, even with > all the computer power on the planet on your side. > > > Occasionally it is possible to reduce the growth constant in > the exponential > to incredibly small values, but I doubt that is the case > here, and even > if it were, then we could not be sure it would always work > after the census > data changed next time.
Actually, it was only "thought" to be NP. I believe there's a way to formulate the same problem in (very large) P-time. I haven't worked out all the details yet, but the problem is topologically equivalent to one I solved for identifying subgraphs in a sport schedule, where the number of "connections" between "adjacent teams" was the number of games played, and "adjancent" meant they played each other. The polynomial solution is very big, but it is not indeterminate, because weakest connection between census blocks is bounded by the maximum "diameter" of a state in units of census blocks. A 'closed form' solution is relatively compact expressed in matrix algebra terms, it is only the implementation that is "hard" in physical implementation because of the wordsize required to represent the cells in powers of the square matrixes that represent the number of connections of a given length. The problem is not NP because the number of iterations required to solve it can be specified beforehand. The solution "looks like" an NP problem, but its separate steps are each of class P, and there are a finite number of steps. P + P +...+ P is still P, albeit a large P. ---- Election-methods mailing list - see http://electorama.com/em for list info