The Complexity of Searching Several Classes of AND/OR Graphs

Abstract

The complexity of searching for a minimum cost solution graph of an AND/OR graph is analyzed for the class of AND/OR graphs repreaentable by a context free grammar with coat functions; finding a minimum coat solution graph ia then equivalent to finding a lowest coat derivation. Several classes of search problems are defined, based on properties of the cost functions and grammar. We show that certain of these classes have different, search complexities- specifically, we show that there are distinct classes for which the complexity of finding a minimum cost solution graph is non-recursive, exponential, NPcomplete, and Q(n 2), where n ia the size of the grammar representing the problem. The correspondence between problem structure and search complexity may serve as a guide for modeling real problems