Complexity for probability logic with quantifiers over propositions
This dense paper consists of four sections and an appendix. The first section contains a brief introduction to probability logic and complexity issues therein as well as a summary of some of the results which are derived at a later point in this paper.NEWLINENEWLINENEWLINEIn Section 2, the author introduces \textit{quantified probability logic}, \(\mathcal{QPL}\), by giving the syntax, the semantics and how it relates to other well-known languages. \(\mathcal{QPL}\) is build up from the usual propositional formulae, polynomials with rational coefficients of \(\mathcal{QPL}\)-terms and Boolean combinations of \(t\leq t'\) where \(t,t'\) are \(\mathcal{QPL}\)-terms. The author goes on to state that \(\mathcal{QPL}\) is an extension of \(\mathcal L_{\mathrm{FHM}-5}\) and a very small fragment of Hoover-Keisler logic.NEWLINENEWLINENEWLINEWith quantifiers present in the language, the validity and satisfiability hierarchies \(\mathrm{Val}-\Pi_i-\mathcal{QPL}\), \(\mathrm{Val}-\Sigma_i-\mathcal{QPL}\), \(\mathrm{Sat}-\Pi_i-\mathcal{QPL}\), and \(\mathrm{Sat}-\Sigma_i-\mathcal{QPL}\) are defined in Section 3. The main result in this section is Theorem~3.6 which states that NEWLINE\[NEWLINE \Pi_0^0\equiv_m \mathrm{Val}-\Sigma_1-\mathcal{QPL} \lneq_m \mathrm{Val}-\Sigma_2-\mathcal{QPL}\leq_m \mathrm{Val}-\Sigma_3-\mathcal{QPL}\leq_m\ldots .NEWLINE\]NEWLINE Section 4 contains a complex proof of NEWLINE\[NEWLINE\text{Theorem 4.1. The validity problem for }\mathcal{QPL}\text{ is }\Pi_1^1\text{-complete}.NEWLINE\]NEWLINE In the appendix, Hilbert's tenth problem for rational coefficients \(\mathrm{DE}(\mathbb Q)\), rather than integer coefficients, is related to the material in this paper. The author shows that \(\mathrm{Sat}-\Pi_0-\mathcal{QPL}\leq_m \mathrm{DE}(\mathbb Q)\).
- Decidability and expressiveness for first-order logics of probability
- Operational characterization of weight-based resource quantifiers via exclusion tasks in general probabilistic theories
- Complexity of fuzzy probability logics
- Possibilistic logic: Complexity and algorithms
- scientific article; zbMATH DE number 4172426 (Why is no real title available?)
- Computational hardness of validity in probability logic
- A note on definability in fragments of arithmetic with free unary predicates
- Collapsing probabilistic hierarchies. I
- Complexity Results for Probabilistic Datalog
- Computability of validity and satisfiability in probability logics over finite and countable models
- Quantifying over events in probability logic: an introduction
- Elementary invariants for quantified probability logic
- An `elementary' perspective on reasoning about probability spaces
- Infinitary calculus for first-order logic of probability with distribution on the domain
- Sharpening complexity results in quantified probability logic
- Quantification over propositional formulas in probability logic: decidability issues
This page was built for publication: Complexity for probability logic with quantifiers over propositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2863169)
