| Towards a Theory of Local and Global in Computation Harold Abelson (2007) | |||||||||||||
Abstract | |||||||||||||
| We formulate the rudiments of a method for assessing the difficulty of dividing a computational problem intQ "independent simpler parts. " This work illustrates measures of complexity which attempt to capture the distinction between "local" and "global " computational problems. One such measure is the covering multi-plicity, or average number of partial computations which take.accoUnt of a given piece of data. Another measure reflects the intuitive notion of a "highly inter-connected"computational problem, for which subsets of the data cannot be processed "in isolation. " These ideas are applied in the setting of Computational geometry to show that the connectivity predicate has unbounded covering multi-plicity and is highly'interconnected; and in the setting of numerical computations to measure the complexity of evaluating polynomials and solving systems of linear equations. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||