[EM] solving the NP-hard problem? no. The CRV approach to gerrymandering.

[Paul Kislanko]

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.