---
title: "The Complexity of Searching Several Classes of AND/OR Graphs"
authors:
  - "Howard E. Motteler"
  - "Laveen N. Kanal"
doi: ""
url: "https://ijcai.org/proceedings/1985/221"
pdf: "https://ijcai.org/proceedings/1985/0221.pdf"
venue: "Proceedings of the Ninth International Joint Conference on Artificial Intelligence"
year: 1985
pages: "1083-1084"
track: "Planning and Search"
keywords:
---

# The Complexity of Searching Several Classes of AND/OR Graphs

Howard E. Motteler, Laveen N. Kanal

*Proceedings of the Ninth International Joint Conference on Artificial Intelligence*, pages 1083-1084.

## Abstract

The complexity of searching for a minimum cost solution graph of an AND/OR graph is analyzed for the dass of AND/OR graphs representable by a context free grammar with cost functions; finding a minimum cost solution graph is then equivalent to finding a lowest cost 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 O(n 2 ), where n is the size of the grammar representing the problem. The correspondence between problern structure and search complexity may serve as a guide for modeling real problems with AND/OR graphs.