Probabilistic satisfiability

DOI10.1016/0885-064X(88)90006-4zbMath0647.68049OpenAlexW2914795094MaRDI QIDQ1104751

Christos H. Papadimitriou, George F. Georgakopoulos, Dimitris J. Kavvadias

Publication date: 1988

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0885-064x(88)90006-4

zbMATH Keywords

linear programming satisfiability problem NP-hard NP-complete polynomial-time algorithms probabilistic logic probabilistic satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Probability and inductive logic (03B48)

Related Items (58)

Probabilistic logic under coherence: complexity and algorithms ⋮ Characterizing consistency in probabilistic logic for a class of Horn clauses ⋮ Computational complexity of queries based on itemsets ⋮ Possibilistic and Probabilistic Logic under Coherence: Default Reasoning and System P ⋮ Boole's conditions of possible experience and reasoning under uncertainty ⋮ Probabilistic logic with independence ⋮ Resolution and the integrality of satisfiability problems ⋮ A linear programming approach to reasoning about probabilities ⋮ Expressive probabilistic description logics ⋮ Assembling a consistent set of sentences in relational probabilistic logic with stochastic independence ⋮ The differential of probabilistic entailment ⋮ NP-containment for the coherence test of assessments of conditional probability: a fuzzy logical approach ⋮ Inconsistency-tolerant reasoning over linear probabilistic knowledge bases ⋮ Explainable acceptance in probabilistic and incomplete abstract argumentation frameworks ⋮ Syntactic reasoning with conditional probabilities in deductive argumentation ⋮ A further step for efficient corrections of inconsistent probabilistic data sets ⋮ Generalized probabilistic satisfiability and applications to modelling attackers with side-channel capabilities ⋮ Measuring inconsistency in probabilistic logic: rationality postulates and Dutch book interpretation ⋮ On measuring inconsistency in definite and indefinite databases with denial constraints ⋮ Probabilistic satisfiability: algorithms with the presence and absence of a phase transition ⋮ Balanced matrices ⋮ Probably partially true: satisfiability for Łukasiewicz infinitely-valued probabilistic logic and related topics ⋮ Sequential decision making with partially ordered preferences ⋮ Optimization and probabilistic satisfiability on nested and co-nested formulas ⋮ Mass Customization and “Forecasting Options’ Penetration Rates Problem” ⋮ Best second order bounds for two-terminal network reliability with dependent edge failures ⋮ On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics ⋮ Consistency checking and querying in probabilistic databases under integrity constraints ⋮ Quantitative Logic Reasoning ⋮ Deciding Koopman's qualitative probability ⋮ Aggregating disparate estimates of chance ⋮ Generalized probabilistic satisfiability ⋮ Compatibility, desirability, and the running intersection property ⋮ Towards classifying propositional probabilistic logics ⋮ An anytime deduction algorithm for the probabilistic logic and entailment problems ⋮ Algorithms for possibility assessments: coherence and extension ⋮ Itemset frequency satisfiability: complexity and axiomatization ⋮ Safe projections of binary data sets ⋮ Merging the local and global approaches to probabilistic satisfiability ⋮ Probability logic and optimization SAT: The PSAT and CPA models ⋮ The basic algorithm for pseudo-Boolean programming revisited ⋮ The complexity of satisfiability in non-iterated and iterated probabilistic logics ⋮ Probabilistic spatio-temporal knowledge bases: capacity constraints, count queries, and consistency checking ⋮ Probabilistic sentence satisfiability: an approach to PSAT ⋮ Automated non-monotonic reasoning in System \textbf{P} ⋮ A polynomial-time fragment of epistemic probabilistic argumentation ⋮ A logic for reasoning about probabilities ⋮ A Propositional CONEstrip Algorithm ⋮ The theory of interval probabilistic logic programs ⋮ Polynomially Computable Bounds for the Probability of the Union of Events ⋮ Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem ⋮ Balanced \(0,\pm 1\) matrices. I: Decomposition ⋮ Axiomatization of frequent itemsets ⋮ New methods for computing inferences in first order logic ⋮ Probabilistic satisfiability and coherence checking through integer programming ⋮ Probabilistic satisfiability with imprecise probabilities ⋮ Logics with Probability Operators ⋮ Justification Logics with Probability Operators

Cites Work

This page was built for publication: Probabilistic satisfiability