  The logic PJ is a probabilistic logic defined by adding (non-iterated)
probability operators to the basic justification logic J. In this paper we
establish upper and lower bounds for the complexity of the derivability problem
in the logic PJ. The main result of the paper is that the complex- ity of the
derivability problem in PJ remains the same as the complexity of the
derivability problem in the underlying logic J, which is {\Pi}p2-complete. This
implies hat the probability operators do not increase the complex- ity of the
logic, although they arguably enrich the expressiveness of the language.
