The complexity of searching several classes of AND/OR graphs
Howard E. Motteler, Laveen N. Kanal · 1985
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