Show simple item record

dc.contributor.authorAbelson, Harolden_US
dc.date.accessioned2004-10-01T20:33:34Z
dc.date.available2004-10-01T20:33:34Z
dc.date.issued1977-09-01en_US
dc.identifier.otherAIM-442en_US
dc.identifier.urihttp://hdl.handle.net/1721.1/5743
dc.description.abstractWe formulate the rudiments of a method for assessing the difficulty of dividing a computational problem into "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 multiplicity, or average number of partial computations which take account of a given piece of data. Another measure reflects the intuitive notion of a "highly interconnected" 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 convering multiplicity and is highly interconnected; and in the setting of numerical computations to measure the complexity of evaluating polynomials and solving systems of linear equations.en_US
dc.format.extent43 p.en_US
dc.format.extent11377128 bytes
dc.format.extent8634466 bytes
dc.format.mimetypeapplication/postscript
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.relation.ispartofseriesAIM-442en_US
dc.titleTowards a Theory of Local and Global in Computationen_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record