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.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-108-84
Published Here
February 17, 2012