The logic $$\mathsf {PJ}$$ is a probabilistic logic defined by adding non-iterated probability operators to the basic justification logic $$\mathsf {J}$$. In this paper we establish upper and lower bounds for the complexity of the derivability problem in the logic $$\mathsf {PJ}$$. The main result of the paper is that the complexity of the derivability problem in $$\mathsf {PJ}$$ remains the same as the complexity of the derivability problem in the underlying logic $$\mathsf {J}$$, which is $$\varPi _2^p$$-complete. This implies hat the probability operators do not increase the complexity of the logic, although they arguably enrich the expressiveness of the language.
['Ioannis Kokkinis']
The Complexity of Non-Iterated Probabilistic Justification Logic