THE COMPUTATIONAL COMPLEXITY OF ASSUMPTION-BASED TRUTH MAINTENANCE SYSTEMS

We define the complexity of the problems that the Assumption-Based TMS (ATMS) solves. Defining the conjunction of the set of input clauses as a Boolean expression, it is shown that an ATMS solves two distinct problems: (l) generating a set of minimal supports (or label) for each database literal; and (2) computing a minimal expression (or set of maximal contexts) from the set of minimal supports. The complexity of determining the set of minimal supports for a set $x$ of literals with respect to a set $X$ of clauses is exponential in the number of assumptions for almost all Boolean expressions, even though a satisfying assignment for the literals occurring in $X$ can be found in linear time. Generating a minimal expression is an NP-hard problem. The ATMS algorithms can be used with many control mechanisms to improve their performance for both problems; however, we argue that manipulating the label set (which is exponential in the number of assumptions) requires considerable computational overhead (in terms of space and time), and that it will be infeasible to solve moderately large problems without problem restructuring.