On Computational Aspects of Maximal Speciﬁcity in Probabilistic Explanation
In the present paper the computational aspects of the formal requirement of maximal speciﬁcity are investigated. This requirement is imposed on rules in the language of propositional classical logic when given a computable rational-valued probability measure over the language. We prove undecidability for several general problems of discovering maximally speciﬁc rules and probability measures for which the collection of all speciﬁc rules is computable; establish decidability of the set of maximally speciﬁc rules if certain natural conditions are met; study the question whether it is possible to uniformly obtain decision procedures in case these conditions hold; estimate the complexity of introduced subclasses of measures in the arithmetical hierarchy.