# The ICICS/CS Reading Room

## UBC CS TR-88-11 Summary

- No on-line copy of this technical report is available.

- The Computational Complexity of Truth Maintenance Systems, July 1988 Gregory M. Provan
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.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.