1984 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.