Affiliations: Communication Systems Engineering Department, Ben Gurion University of The Negev, Israel E-mail: avin@cse.bgu.ac.il | Department of Software Engineering, Jerusalem College of Engineering (JCE), Israel E-mail: rbz@jce.ac.il
Note: [] Part of this work was done while the author was a visiting scholar in the division of engineering and applied sciences, Harvard university, Cambridge, MA.
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.
