The Complexity of the Diagnosis Problem

A report presents a study of the complexity of an algorithm that performs model-based diagnosis of a complex hardware system. [In model-based diagnosis, an algorithm detects logical inconsistencies between observational data and a description (mathematical model) of the system.] In the study, the problem of detecting logical inconsistencies is transformed into the problem of finding prime implicants of a monotone Boolean function. This transformation enables utilization of the welldeveloped machinery of Boolean function theory, not directly accessible in the logical approach: one can work with monotone Boolean functions described by polynomial-size monotone circuits instead of attempting to deal with logical objects and performing exhaustive searches in order to extract all desired information. One especially notable result achieved in this study through the Boolean-function approach is the first analytical proof that the diagnosis problem is NP-complete. The report asserts that the discovery of the connection between diagnosis and the Boolean functions may afford new means to solve the diagnosis problem — in particular, to develop diagnostic algorithms that take super-polynomial amounts of time, in contrast to the exponential amounts of time heretofore needed to solve NP-complete problems.