zbMATH — the first resource for mathematics

Probabilistic satisfiability. (English) Zbl 0647.68049
Summary: We study the following computational problem proposed by N. J. Nilsson [Artif. Intell. 28, 71-87 (1986; Zbl 0589.03007)]: Several clauses (disjunctions of literals) 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 problem is a generalization of the satisfiability problem for propositional calculus it is immediately NP-hard. We show that it is NP- complete even when there are at most two literals per clause (a case which is polynomial time solvable in the non-probabilitic case). We use arguments from linear programming and graph theory to derive polynomial- time algorithms for some interesting special cases.

68Q25 Analysis of algorithms and problem complexity
03B48 Probability and inductive logic
90C05 Linear programming
Full Text: DOI
[1] Garey, M.R; Johnson, D.S, Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman, New York · Zbl 0411.68039
[2] Garey, M.R; Johnson, D.S; Stockmeyer, L.J, Some simplified NP-complete problems, Theor. comput. sci., 1, 237-267, (1976) · Zbl 0338.05120
[3] Grötschel, M; Lovàsz, L; Schruver, S, The ellipsoid method and its consequences in combinatorial optimization, ()
[4] Honeyman, P; Ladner, R.E; Yannakakis, M, Testing the universal instance assumption, Inf. process. lett., 10, 1, 14-19, (1980) · Zbl 0422.68048
[5] Karp, R.M; Papadimitriou, C.H, On linear characterization of combinatorial optimization problems, SIAM J. comput., 11, 4, 620-632, (1982) · Zbl 0505.65020
[6] Kavvadias, D, (), in preparation
[7] Khachian, L.G, A polynomial algorithm for linear programming, Dokl. akad. nauk. SSSR, 244, 5, 1093-1096, (1979) · Zbl 0414.90086
[8] Nau, D.S, Expert computer systems, Comput. surv., 63-85, (1983)
[9] Nilsson, N, Probabilistic logic, () · Zbl 0589.03007
[10] Papadimitriou, C.H; Steiglitz, K, Combinatorial optimization: algorithms and complexity, (1982), Prentice-Hall Englewood Cliffs, N.J · Zbl 0503.90060
[11] Prade, H, A computational approach to approximate and plausible reasoning with applications to expert systems, IEEE trans. PAMI, 7, 3, (1985) · Zbl 0565.68089
[12] \scTsitsiklis J. N. (1986), Personal communication, February.
[13] Zadeh, L.A, Fuzzy sets, Inform. contr., 8, 338-353, (1971) · Zbl 0139.24606
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.