ISSN:
1573-7470
Keywords:
Probabilistic logic
;
reasoning about probabilities
;
linear programming
;
algorithms
;
complexity
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We continue our study, initiated in [9], of the following computational problem proposed by Nilsson: Several clauses (Boolean functions of several variables) are given, and for each clause the probability that the clause is true is specified. We are asked whether these probabilities are consistent. They are if there is a probability distribution on the truth assignments such that the probability of each clause is the measure of its satisfying set of assignments. Since this is a generalization of the satisfiability problem of predicate calculus, it is immediately NP-hard. In [9] we showed certain restricted cases of the problem to be NP-complete, and used the Ellipsoid Algorithm to show that a certain special case is in P. In this paper we use the Simplex method, column generation techniques, and variable-depth local search to derive an effective heuristic for the general problem. Experiments show that our heuristic performs successfully on instances with many dozens of variables and clauses. We also prove several interesting complexity results that answer open questions in [9] and motivate our approach.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01531078
Permalink
