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.

This work was done by Farrokh Vatan of Caltech for NASA’s Jet Propulsion Laboratory. To obtain a copy of the report, “The Complexity of the Diagnosis Problem,” access the Technical Support Package (TSP) free on-line at www.nasatech.com/tsp under the Information Sciences category. NPO-30315


This Brief includes a Technical Support Package (TSP).

Unfortunately the TSP The Complexity of the Diagnosis Problem (reference NPO-30315) appears to be missing from our system.

Please contact This email address is being protected from spambots. You need JavaScript enabled to view it. for assistance in retrieving it.

Don't have an account? Sign up here.



NASA Tech Briefs Magazine

This article first appeared in the April, 2002 issue of NASA Tech Briefs Magazine.

Read more articles from the archives here.