Hybrid Probabilistic Programs: Algorithms and Complexity
  Hybrid Probabilistic Programs (HPPs) are logic programs that allow the
programmer to explicitly encode his knowledge of the dependencies between
events being described in the program. In this paper, we classify HPPs into
three classes called HPP_1,HPP_2 and HPP_r,r>= 3. For these classes, we provide
three types of results for HPPs. First, we develop algorithms to compute the
set of all ground consequences of an HPP. Then we provide algorithms and
complexity results for the problems of entailment ("Given an HPP P and a query
Q as input, is Q a logical consequence of P?") and consistency ("Given an HPP P
as input, is P consistent?"). Our results provide a fine characterization of
when polynomial algorithms exist for the above problems, and when these
problems become intractable.
