An upper bound on computing all X-minimal models

Abstract

The problem of computing X-minimal models, that is, models minimal with respect to a subset X of all the atoms in a theory, is relevant for many tasks in Artificial Intelligence. Unfortunately, the problem is NP-hard. In this paper we present a non-trivial upper bound for the task of computing all X-minimal models: we show that all the X-minimal models of a propositional theory 𝒯 can be found in time time-ord-mod(𝒯)+O(#DMinModX(𝒯)n ${\pmatrix{{n}\\{\lfloor \frac{n}{2}\rfloor}}}$ , where time-ord-mod(𝒯) is the time it takes to find all the models of 𝒯 in a particular order, #DMinModX(𝒯) is the number of different X-minimal models of T, and |X|=n.