Academic Commons

Reports

An Analysis of Abstraction in Problem Solving

Korf, Richard E.

A quantitative model of abstraction in problem solving is presented which explains how and to what extent it reduces the amount of search necessary to solve a problem. It is shown that a single level of abstraction can reduce search time by a factor of the square root of the size of the original space. Multiple hierarchical levels of abstraction can reduce the search complexity of a problem from linear in the size of the original problem space to logarithmic.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-108-84
Published Here
February 17, 2012
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.