01442nas a2200145 4500008004100000245005100041210005100092300001200143490000800155520099900163653002001162100002001182700001901202856007501221 2012 eng d00aLower complexity bounds in justification logic0 aLower complexity bounds in justification logic a888-9050 v1633 aJustification Logic studies epistemic and provability phenomena by introducing justifications/proofs into the language in the form of justification terms. Pure justification logics serve as counterparts of traditional modal epistemic logics, and hybrid logics combine epistemic modalities with justification terms. The computational complexity of pure justification logics is typically lower than that of the corresponding modal logics. Moreover, the so-called reflected fragments, which still contain complete information about the respective justification logics, are known to be in NP for a wide range of justification logics, pure and hybrid alike. This paper shows that, under reasonable additional restrictions, these reflected fragments are NP-complete, thereby proving a matching lower bound. The proof method is then extended to provide a uniform proof that the corresponding full pure justification logics are $\Pi^p_2$-hard, reproving and generalizing an earlier result by Milnikel.10aLogic of Proofs1 aBuss, Samuel, R1 aKuznets, Roman uhttp://www.math.ucsd.edu/~sbuss/ResearchWeb/rlp_lower/APAL09_final.pdf