Extending the Computational Horizon: Effective Distributed Resource-Bounded Computation for Intractable Problems

A number of combinatorial problems of interest to computational economists, such as some two-sided matching problems, belong to the complexity class NP. The best known solutions to these problems require exponential computation time in the size of the input, and are intractable in practice except for very small input size. We present an overview of a new distributed-computation technique called "nagging" that, while still exponential, allows one to harness multiple processors to extend the size of the largest solvable problem in a resource-bounded environment. Nagging requires relatively infrequent and brief interprocessor communication, is naturally tolerant (i.e., unaffected by the dynamic loss of processing elements), and exceptionally scalable in practice (i.e., robust in the presence of high message latencies, and, therefore, suitable for use in very large networks).