Parallel hardware for constraint satisfaction," Proc., DARPA Image Understanding Workshop

A parallel implementation of constraint satisfac-tion by arc consistency is presented. The im-plementation is constructed of standard digital hardware elements, used in a very fine-grained, massively parallel style. As an example of how to specialize the design, a parallel implementation for solving graph isomorphism with arc consis-tency is also given. Complexity analyses are given for both circuits. Worst case running time for the algorithms turns out to be linear in the number of variables n and labels a, O(an), and if the I/O must be serial, it will dominate the computation time. Fine-grained parallelism trades off time complexity for space complexity, but the number of gates re-quired is only O(a2n2). I