The Satisfiability and Validity Problems for Probabilistic Computational Tree Logic are Highly Undecidable
Miroslav Chodil, Antonín Kučera · 2025
Read The Satisfiability and Validity Problems for Probabilistic Computational Tree Logic are Highly Undecidable by Miroslav Chodil, Antonín Kučera (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-19207.txt.
Introduction
Miroslav Chodil and Antonín Kučera wrote this 2025 paper that settles a thirty year open question in logic for systems with chance. The logic, called PCTL, states facts about systems whose steps follow fixed odds, modeled as Markov chains. Two basic questions ask whether a formula can hold at all, and whether it must always hold.
The authors prove that both questions are highly undecidable. That means no sound and complete proof system can exist for this logic. The result sits beyond the whole ladder of problems that counting based methods can solve. It closes a line of work that many teams had tried over three decades.
Catalog record
| CREATOR | Miroslav Chodil, Antonín Kučera |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 141 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-19207
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Satisfiability and Validity Problems for Probabilistic Computational Tree Logic are Highly Undecidable Miroslav Chodil, Antonín Kučera Abstract The Probabilistic Computational Tree Logic (PCTL) is the main specification formalism for discrete probabilistic systems modeled by Markov chains. Despite serious research attempts, the decidability of PCTL satisfiability and validity problems remained unresolved for 30 years. We show that both problems are highly undecidable , i.e., beyond the arithmetical hierarchy. Consequently, there is no sound and complete deductive system for PCTL. Faculty of Informatics, Masaryk University, Brno, [email protected] of Informatics, Masaryk University, Brno, [email protected] ccs Theory of computation Modal and temporal logics keywords Satisfiability, temporal logics, probabilistic CTL † † runningtitle: PCTL Satisfiability and Validity † † runningauthor: Chodil and Kučera † † copyright: Miroslav Chodil and Antonín Kučera † † funding: The presented work received funding from the European Union’s Horizon Europe program under the Grant Agreement No. 101087529. † † editors: Keren Censor-Hillel, Fabrizio Grandoni, Joel Ouaknine, and Gabriele Puppis † † event-title: 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) † † event-shorttitle: ICALP 2025 † † event-acronym: ICALP † † year: 2025 † † event-date: July 8–11, 2025 † † event-location: Aarhus, Denmark † † series-volume: 334 † † articleno: 163 1 Introduction Algorithms for checking the satisfiability/validity of formulae in a given logic have received significant attention from the very beginning of computer science. The satisfiability/validity problems are closely related to each other because for most logics we have that \varphi is valid iff \neg\varphi is not satisfiable. The decidability of the validity problem for first-order logic, also known as the Entscheidungsproblem , was posed by Hilbert and Ackermann in 1928 and aswered negatively by Church [ 8 ] and Turing [ 23 ] in 1936. Later, Trakhtenbrot [ 22 ] demonstrated that the finite satisfiability problem for first-order logic is also undecidable. Consequently, the finite validity problem is not even semi-decidable, and hence there is no sound and complete deductive system proving all finite valid first-order formulae. For propositional logic, the satisfiability and validity are the canonical NP and \mathbf{coNP} complete problems [ 9 ] . The satisfiability and validity problems have also been intensively studied for temporal logics such as LTL, CTL, CTL ∗ , or the modal \mu -calculus, and their computational complexity has been fully classified (see, e.g., [ 10 , 21 ] ). Temporal logics are interpreted over transition systems , i.e., directed graphs where the vertices correspond to the states of an abstract non-deterministic program, and the edges model the atomic computational steps. Even for the most expressive logic of the modal \mu -calculus [ 14 ] , the satisfiability/validity problems are decidable and EXPTIME -complete, and every satisfiable formula \varphi has a model whose size is at most exponential in |\varphi| (this is known as “the small model property” [ 15 ] ). Furthermore, there is a sound and complete deductive system for the modal \mu -calculus [ 24 ] . Probabilistic temporal logics , such as PCTL or PCTL ∗ [ 11 ] are interpreted over discrete-time Markov chains modelling probabilistic programs . Despite numerous research attempts resulting in partial positive results (see Related work), the decidability of the satisfiability/validity problems for PCTL has remained unresolved for more than 30 years. In this paper, we prove that both problems are highly undecidable (i.e., beyond the arithmetical hierarchy), even for a simple PCTL fragment where the path connectives are restricted to \operatorname{\boldsymbol{\mathtt{F}}} and \operatorname{\boldsymbol{\mathtt{G}}} . Consequently, there is no sound and complete deductive system for PCTL. Related work. Unlike non-probabilistic temporal logics, PCTL does not have the small model property. In fact, one can easily construct satisfiable PCTL formulae without any finite model (see, e.g., [ 3 ] ). Hence, the PCTL satisfiability/validity problems have also been studied in their finitary variants. The first positive decidability results have been obtained for the qualitative fragment of PCTL, where the range of admissible probability constraints is restricted to {=}0 , {>}0 , {=}1 , and {<}1 (see Section 2 for details). The satisfiability/validity for qualitative PCTL is EXPTIME -complete, and the same holds for finite satisfiability/validity [ 19 , 13 , 16 ] . Furhermore, a finite description of a model for a satisfiable qualitative PCTL formula is constructible in exponential time [ 3 ] . The underlying proof techniques are similar to the ones used for non-probabilistic temporal logics. The finite satisfiability is decidable also for certain quantitative PCTL fragments with general probability constrains [ 17 , 5 , 7 ] . The underlying arguments are mostly based on establishing an upper bound on the size of a model for a satisfiable formula of the considered fragment (the existence of a model can then be expressed in the existential fragment of first-order theory of the reals, which is known to be in PSPACE [ 4 ] ). More concretely, in [ 5 ] it is shown that every formula \varphi of the bounded fragment of PCTL, where the validity of \varphi in a state s depends only on a bounded prefix of a run initiated in s , has a bounded-size tree model. In [ 17 ] , several PCTL fragments based on \operatorname{\boldsymbol{\mathtt{F}}} and \operatorname{\boldsymbol{\mathtt{G}}} operators are studied. For each of these fragments, it is shown that every finite satisfiable formula has a bounded-size model where every non-bottom SCC is a singleton. For some of these fragments, it is shown that every satisfiable formula has a finite model, which yields the decidability of the (general) satisfiability problem. In [ 7 ] , more abstract decidability results about finite PCTL satisfiability based on isolating the progress achieved along a chain of visited SCCs are presented. A variant of the bounded satisfiability problem, where transition probabilities are restricted to \{\frac{1}{2},1\} , is proven NP -complete in [ 1 ] . A recent result of [ 6 ] says that the finite satisfiability problem for unrestricted PCTL is undecidable . For a given Minsky machine, a PCTL formula \psi is constructed so that every reachable configuration of the machine corresponds to a special state of a model. Hence, \psi is always satisfiable, and \psi has a finite model iff the set of reachable configurations of the machine is finite. Hence, the construction does not imply the undecidability of general PCTL satisfiability, and some of the crucial tools used in [ 6 ] apply only to finite Markov chains (see Section 4 for more comments). Our contribution. We show that the satisfiability problem for PCTL is hard for the \Sigma_{1}^{1} level of the analytical hierarchy. Consequently, the PCTL validity problem is \Pi_{1}^{1} -hard. These results hold even for the PCTL fragment where only the path connectives \operatorname{\boldsymbol{\mathtt{F}}},\operatorname{\boldsymbol{\mathtt{G}}} are allowed. The proof is based on encoding the existence of a recurrent computation of a given non-deterministic two-counter machine \mathcal{M} by an effectively constructible PCTL formula \varphi_{\mathcal{M}} . The overall structure of \varphi_{\mathcal{M}} and the main underlying concepts are introduced in Section 3 . In particular, in Section 3.2 , we identify a fundamental obstacle that needs to be overcome when constructing \varphi_{\mathcal{M}} . This is achieved by utilizing some concepts of convex geometry, and the solution is presented in Section 4 . The