Probabilistic Logic Programming with Conditional Constraints

We introduce a new approach to probabilistic logic programming in which probabilities are defined over a set of possible worlds. More precisely, classical program clauses are extended by a subinterval of [0,1] that describes a range for the conditional probability of the head of a clause given its body. We then analyze the complexity of selected probabilistic logic programming tasks. It turns out that probabilistic logic programming is computationally more complex than classical logic programming. More precisely, the tractability of special cases of classical logic programming generally does not carry over to the corresponding special cases of probabilistic logic programming. Moreover, we also draw a precise picture of the complexity of deciding and computing tight logical consequences in probabilistic reasoning with conditional constraints in general. We then present linear optimization techniques for deciding satisfiability and computing tight logical consequences of probabilistic logic programs. These techniques are efficient in the special case in which we have little relevant purely probabilistic knowledge.We finally show that probabilistic logic programming under certain syntactic and semantic restrictions is closely related to van Emden's quantitative deduction, and thus has computational properties similar to classical logic programming. Based on this result, we present an efficient approximation technique for probabilistic logic programming.