The Complexity of Searching Several Classes of AND/OR Graphs

1. Introduetion

The complexity of A.I. search procedures is a topic of current interest [13,2,6]. In this paper we analyze the complexity of searching several classes of AND/OR graphs. The AND/OR graphs in which we are interested are represented by the composite decision process (CDP) [4,8]. This is a generalization of the sequential decision process (SDP) proposed by Karp and Held in [5]. The classes of AND/OR graphs represented by the composite decision process are a model for a wide variety of search procedures, problems in pattern recognition, and dynamic programming problems. Applications and examples of relevance to practical problems may t>e found in [4,8,9].

A CDP is defined by giving a context-free grammar, and a cost function associated with each production and terminal symbol. This is essentially Knuth's "synthesized attributes" [7], with a different motivation. The minimalization problern is to find a lowest cost parse tree for any string the grammar might derive. This is equivalent to the problern of finding a minimum cost solution graph of the AND/OR graph corresponding to the grammar [11].

The correspondence between AND/OR graphs and context free grammars is that connectors (the AND arcs) correspond to produc­ tions, and OR arcs correspond to a choice of productions. The simple grammar and graph of figure 1 shows the correspondence. This cor­ respondence was first noted by Hall [3]; following the treatment in Nilsson, nodes arenot restricted tobe only of types AND or OR [12]. Our AND/OR graphs may contain cycles, and in general a solution graph may include a walk araund some cycle any number of times. Thinking in terms of grammars, a solution graph is just a parse tree; a solution graph may be much !arger than the grammar graph, and there may be infinitely many parse/solution trees. Figure 1 gives two solution trees for the AND/OR graph shown there; note that the !arger of the two aolution trees has minimal cost.

*Research supported by NSF grants to the Machine Intelligence and Pattern Analysis Lab., Dept. of Computer Science, University of Maryland.

THE COMPLEXITY OF SEARCHING SEVERAL GLASSES OF AND/OR GRAPHS

Howard E. Matteier Laveen N. Kanal *

The Machine lntelligence and Pattern Analysis Labaratory Department of Computer Science University of Maryland College Park, MD 20742

A CDP with the associated AND/ OR graph.

Two solution trees; nodes are paired with backed up costs.

Figure 1. Example of a CDP and solution graphs

We define classes of CDPs based on properties of the cost func­ tions and the grammar, and for each such class analyze the complex­ ity of the minimalization problem. These classes are intended to have some realistic motivation. For example, positive monotone CDPs [8] include generalizations of Dijkstra's algorithm. f-bounded CDPs are a formulation of bounded search. Suppose n is the size of some CDP. In the f-bounded CDP, we assume that any possible minimum value must occur in a tree with no more than f(n) nodes. Acyclic CDPs are just the common restriction that the underlying AND /OR graph have no cycles.

The size of a CDP is defined as the size of the grammar (the sum of the lengths of the productions, written as ]G]) . Weshallshow upper and lower bounds on the complexity of solving the minimalization problern for various classes of CDP. An upper bound expressed as some function f means that every member of the class can be solved in f(]G]) steps, and a lower bound of f means that infinitely many members of a class require more than f( ]G]) steps. The notion of "step of a computation" and bounding computation time are formalized in Aha, et al. [1]. We assume their "logarithmic cost criterion", where the cost of storing or manipulating a !arge number is then proportional to the length of the number. We assume unit cost for storing or manipulating a single grammar symbol, and cost proportional to the length of a string for manipulating a string of such symbols.

If the cost functions are easy to compute, we can ignore them in analyzing search complexity. The notion of "easy to compute" must be made precise, because if we just ignore the complexity of computing the cost functions, our conclusions may not be correct. For example, if we did not consider the complexity of computing the cost functions in giving proofs of upper bounds, by solving a CDP we could compute any recursive function with a constant cost. For Iet f be some such function. Define cost functions c(d) = d, giving the value of a digit as its cost, and t(xt, ... ,xk) = f o g(xt,···oxk), where g translates a string of digits of length k to an integer. Let G be the single production St -+ x, where x is the string of k digits representing x. Then to compute f(x), find the minimum (the only) value of this CDP. If we charge only for search steps and we have only one step, then we have a constant cost. This difliculty is circumvented by requiring our CDPs tobe "honest", that is for some function f, we guarantee that no computation of a cost function t takes more than f(!GI) steps. Here we shall assume (unless otherwise noted) that every CDP is honest for some fixed polynomial h. This restriction is not necessary for proofs of lower bounds, as computation of the cost functions can only add to the complexity.

3. The Complexity of Several Classes of CDPs

The complexity of the natural CDP, acyclic CDPs, p-bounded CDPs for some polynomial p, and monotone CDPs are analyzed in this section. Figure 2 shows the structural relationships among various CD Ps considered here. Figure 3 summarizes our results, showing the relationship of the complexity of the various minimalization problems. In the structure hierarchy, the positive monotone CDP is contained in the ACDP only in the sense that any minimum cost solution graph of the former is guaranteed to be acyclic; an arbitrary parse tree of a positive monotone CDP may not be acyclic. Formal proofs and further examples are presented in [11]; we present only an outline here.

If the range of cost functions isover real numbers, there may be no minimum cost parse tree. Restricting the range of the cost functions to natural numbers guarantees that a solution tree will exist, but as the following theorem shows, there may still be no effective way to find it.

Theorem 1. The rninirnalization problern for the natural CDP is not recursive.

Proof. The problern of generating the shortest program P that outputs m and halts is reduced to a minimization problern for a CDP. Detailsare presented in [11]. ~

This result is not surprising, since L( G) may be infinite, giving an unbounded number of parse trees whose backed up value rnust be tested. If we try to find the minimum by simply generating and testing parse trees, and save the lowest value encountered so far as min, there is in general no guarantee that if we stop at any given point, the next, untested, value may not be lower than min. The obvious way to get a decidable problern is to simply bound the space of all parse trees ( or all parse trees that could possibly contribute to a minimum) in some way. The ACDP, f-bounded CDPs and MCDPs bound their search space in various ways, giving decidable problems of varying complexity.

To show an upper bound on the time to solve an ACDP, we must first find a bound for the size of any parse tree and the number of distinct parse trees that may be generated by an acyclic context free grammar. Let exp2(x) = 2 2 ', to keep our exponents from stacking too high. The following Iemmas and theorem are proved in [11].

Lemma 1. No parse tree for an acyclic grarnrnar G has rnore than 21GI - l- 1 nodes.

Lemma 2. No acyclic grarnrnar G generates rnore than exp2(([G[- 1) 2 ) distinct parse trees.

Theorem 2. The rninirnalization problern for any rnernber of ACDP rnay be solved in O(exp2([G[ 2 - 2)) steps, and requires rnore than 2IGI/ 3 steps for in6nitely rnany rnernbers of ACDP.

Proof of the upper bound is by outlining a procedure MIN A ( Z) that finds a minimal cost derivation for any Z E ACDP by doing an exhaustive search of the space of all possible parse trees. To show the lower bound it is suflicient to show that there are infinitely many acyclic grammars where every parse tree has more than 2IGI/ 3 nodes. ~

A simplegrammarG with on the order of exp2([G[) distinct parse trees is presented in [11]. With such a potentially !arge search space, it would be reasonable to expect (although this does not constitute a proof) that there are infinitely many ACDPs which require on the order of exp2([GI) steps for their solution.

We conclude that the minimalization problern for ACDPs (and f-bounded CDPs for exponential f) is not practically solvable. The difliculty arises from the very compact representation of !arge trees given by an acyclic grammar. We now consider other means of bound­ ing the size of the search tree. The following theorem shows that even if we bound the size of the tree by a polynomial in the size of the grammar, we still have a hard problem.

Theorem 3. For every polynornial p such that p(x) :::0: x, the rnini­ malization problern for the p-bounded CDP is NP-complete.

Proof. Assurne p is some fixed polynomial, p(x) :::0: x. We first show the problern is NP-hard [1,10]. The knapsack problern with inte­ ger weights is easily reduced to a p-bounded CDP. (That is, we show that if we can solve the minimalization problem, then we can solve the knapsack problem, which is known to be NP-complete.) Details are presented in [11[. The same reduction shows that acydic CDPs and the natural CDP are NP-hard, since the CDP we have defined is a member of these dasses. The acydic and natural CDP dasses do not appear to be NP-complete, since there is no obvious nondeterministic polynomial time algorithm that solves them.

To complete the proof it must be shown that p-bounded CDP minimalization can be solved by a nondeterministic algorithm in poly­ nomial time. This is done by defining an algorithm which repeatedly makes a nondeterministic selection (a guess) of a production until some string is derived, and for each such string tests its backed up value aginst successively increasing values of a counter . It is not suf­ ficient to simply guess a parse tree and return its value; this would produce a tree with fewest possible nodes, but not necessarily minimum cost . 181

Finally, we consider an easily solved dass of CDPs. A positive monotone CDP has all ti monotone nondecreasing, and also satisfying ti(x1, ... , Xk) 2: x;, 1 ~ j ~ k.

Theorem 4. The minimalization problern for the positive monotone CDP can be solved in O([G[ 2 ) steps.

Proof is by presenting an algorithm and proving its runtime and correctness. The proof dosely parallels proofs of the runtime and correctness of various algorithms that it generalizes, e.g., Dijkstra's algorithm and certain dynamic programming problems. A similar algorithm appears in [8]. Detailsare presented in [11]. 181

Conclusions

Slight variations in the structure of the cost functions or gram­ mar can cause a !arge change in the complexity of the minimalization problem. H only a single cost function fails to be monotone increas­ ing, the result is a problern of much greater complexity. These results have the following practical application: When modeling some real problern as an AND/OR graph search, every effort should be made to create a. graph model in the structural dass with lowest search com­ plexity. I'he proof of a !arge lower bound for the complexity of some problern is not necessarily the last word as to whether the problern is practically solvable. This sort of analysis does not take into ac­ count the distribution of members of a dass which are most difficult. Even though we know there are infinitely many difficult members, they could still be very rare, i.e., most members of the dass could be easily solved.

Positive monotone CDPs are the only easily solvable CDPs con­ sidered here. There is an interesting natural dass of CDPs, which satisfy only the monotone restriction; these are considered in [8,9]. Let c· (W) be the lowest cost for any tree rooted at W; the monotone CDP satisfies the equations

• H W isaterminal node, then c*(W) = c(W),
• 2 H W is a nonterminal node, we have c· (W) = min{ ti (c* (XI), ... , c*(Xk;) I Pi= w-+ xl·· .Xk;}·

We conjecture that the monotone CDPs are not in generat solv­ able in polynomial time (in the context of definitions and restrictions presented here). It would also be of interest to find other natural or easily definable dasses of CDPs with an easily solved minimalization problem.