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

DOI10.1007/S10472-018-9593-YzbMATH Open1459.03027arXiv1712.00810OpenAlexW3099252540MaRDI QIDQ1783740FDOQ1783740

Authors: Ioannis Kokkinis 

Publication date: 21 September 2018

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

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.

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

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

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)

Cites Work

• A new polynomial-time algorithm for linear programming
• Modal logic
• Title not available (Why is that?)
• Title not available (Why is that?)
• Probabilistic logic
• Explicit provability and constructive semantics
• Reasoning about knowledge and probability
• A logic for reasoning about probabilities
• Title not available (Why is that?)
• Title not available (Why is that?)
• A guide to completeness and complexity for modal logics of knowledge and belief
• Some first-order probability logics
• A logic with approximate conditional probabilities that can model default reasoning
• Probability logics
• Probability logics. Probability-based formalization of uncertain reasoning
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Probabilistic satisfiability
• Title not available (Why is that?)
• Justification logic with approximate conditional probabilities
• The complexity of non-iterated probabilistic justification logic
• NEXP-completeness and universal hardness results for justification logic
• First steps towards probabilistic justification logic
• Probabilistic justification logic

Cited In (7)

• Multi-agent logics for reasoning about higher-order upper and lower probabilities
• Complexity Results for Probabilistic Datalog
• Logics with Probability Operators
• The complexity of non-iterated probabilistic justification logic
• 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)