A Final Determination of the Complexity of Current Formulations of Model-Based Diagnosis (Or Maybe Not Final?)

There are three parts to this paper. First, I present what I hope is a conclusive, worst-case, complexity analysis of two well-known formulations of the Minimal Diagnosis problem — those of [Reiter 87] and [Reggia et al., 85]. I then show that Reiter's conflict-sets solution to the problem decomposes the single exponential problem into two problems, each exponential, that need be solved sequentially. From a worst case perspective, this only amounts to a factor of two, in which case I see no reason to prefer it over a simple generate-and-test approach. This is only emphasized with the results of the third part of the paper. Here I argue for a different perspective on algorithms, that of expected, rather than worst-case performance. From that point of view, a sequence of two exponential algorithms has lesser probability to finish early than a single such algorithm. I show that the straightforward generate-and-test approach may in fact be somewhat attractive as it has high probability to conclude in a polynomial time, given a random problem instance.