Probabilistic Logic Programming

We present a new approach to probabilistic logic programs with a possible worlds semantics. Classical program clauses are extended by a subinterval of [0,1] that describes the range for the conditional probability of the head of a clause given its body. We show that deduction in the defined probabilistic logic programs is computationally more complex than deduction in classical logic programs. More precisely, restricted deduction problems that are P-complete for classical logic programs are already NP-hard for probabilistic logic programs. We then elaborate a linear programming approach to probabilistic deduction that is efficient in interesting special cases. In the best case, the generated linear programs have a number of variables that is linear in the number of ground instances of purely probabilistic clauses in a probabilistic logic program.