The complexity of satisfiability in non-iterated and iterated probabilistic logics

DOI10.1007/S10472-018-9593-YMaRDI QIDQ1783740zbMATH OpenOpenAlexFDO

Authors Ioannis Kokkinis

Publication date 21 September 2018

Published in Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.00810

zbMATH Keywords

computational complexitysatisfiabilityjustification logicprobabilistic logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability and inductive logic (03B48) Logics of knowledge and belief (including belief change) (03B42)

Abstract: Let L be some extension of classical propositional logic. The non-iterated probabilistic logic over L, is the logic PL that is defined by adding non-nested probabilistic operators in the language of L. For example in PL we can express a statement like "the probability of truthfulness of A is at 0.3" where A is a formula of L. The iterated probabilistic logic over L is the logic PPL, where the probabilistic operators may be iterated (nested). For example, in PPL we can express a statement like "this coin is counterfeit with probability 0.6". In this paper we investigate the influence of probabilistic operators in the complexity of satisfiability in PL and PPL. We obtain complexity bounds, for the aforementioned satisfiability problem, which are parameterized in the complexity of satisfiability of conjunctions of positive and negative formulas that have neither a probabilistic nor a classical operator as a top-connective. As an application of our results we obtain tight complexity bounds for the satisfiability problem in PL and PPL when L is classical propositional logic or justification logic.

Recommendations

• The complexity of non-iterated probabilistic justification logic
• A probabilistic logic between \(LPP_1\) and \(LPP_2\)
• Probably partially true: satisfiability for Łukasiewicz infinitely-valued probabilistic logic and related topics
• On the satisfiability of some simple probabilistic logics

Cites work

• scientific article; zbMATH DE number 1670490 (Why is no real title available?)
• scientific article; zbMATH DE number 3854804 (Why is no real title available?)
• scientific article; zbMATH DE number 3827203 (Why is no real title available?)
• scientific article; zbMATH DE number 3657792 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1114348 (Why is no real title available?)
• scientific article; zbMATH DE number 1873277 (Why is no real title available?)
• scientific article; zbMATH DE number 6302917 (Why is no real title available?)
• A guide to completeness and complexity for modal logics of knowledge and belief
• A logic for reasoning about probabilities
• A logic with approximate conditional probabilities that can model default reasoning
• A new polynomial-time algorithm for linear programming
• Explicit provability and constructive semantics
• First steps towards probabilistic justification logic
• Justification logic with approximate conditional probabilities
• Modal logic
• NEXP-completeness and universal hardness results for justification logic
• Probabilistic justification logic
• Probabilistic logic
• Probabilistic satisfiability
• Probability logics
• Probability logics. Probability-based formalization of uncertain reasoning
• Reasoning about knowledge and probability
• Some first-order probability logics
• The complexity of non-iterated probabilistic justification logic

Cited in

(7)

• Multi-agent logics for reasoning about higher-order upper and lower probabilities
• Complexity Results for Probabilistic Datalog
• The complexity of non-iterated probabilistic justification logic
• Logics with Probability Operators
• Justification Logics with Probability Operators
• A probabilistic logic between \(LPP_1\) and \(LPP_2\)
• Computability of validity and satisfiability in probability logics over finite and countable models

This page was built for publication: The complexity of satisfiability in non-iterated and iterated probabilistic logics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1783740)