The Complexity of Searching Several Classes of AND/OR Graphs
Proceedings of the Ninth International Joint Conference on Artificial Intelligence. Planning and Search. 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.
@inproceedings{ijcai1985p221,
title = {The Complexity of Searching Several Classes of AND/OR Graphs},
author = {Motteler, Howard E. and Kanal, Laveen N.},
booktitle = {Proceedings of the Ninth International Joint Conference on
Artificial Intelligence, {IJCAI-85}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Aravind Joshi},
pages = {1083--1084},
year = {1985},
note = {Planning and Search},
url = {https://ijcai.org/proceedings/1985/221},
}
TY - CPAPER TI - The Complexity of Searching Several Classes of AND/OR Graphs AU - Motteler, Howard E. AU - Kanal, Laveen N. T2 - Proceedings of the Ninth International Joint Conference on Artificial Intelligence, IJCAI-85 PB - International Joint Conferences on Artificial Intelligence PY - 1985 SP - 1083 EP - 1084 UR - https://ijcai.org/proceedings/1985/221 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
