Journal article:

    Samuel R. Buss and Roman Kuznets.
    "Lower Complexity Bounds in Justification Logic"
    Annals of Pure and Applied Logic 163, 7 (2012) 888-905.

    Download manuscript: PDF.

Abstract for full paper:  Justification 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_2^p$-hard, reproving and generalizing an earlier result by Milnikel.


Conference proceedings article:

    Samuel R. Buss, Roman Kuznets.
    "The NP-Completeness of Reflected Fragments of Justification Logics"
   Logical Foundations of Computer Science, LFCS'09,
    Lecture Notes in Computer Science #5407, Springer-Verlag, 2009, pp. 122-136.

This is an earlier version of the paper, with only part of the results.

    Download LFCS conference version: PDF.

Abstract for conference version:  Justification 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 that 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.

Conference presentation:

      "The NP-Completeness of Reflected Fragments of Justification Logics".
   
Logical Foundations of Computer Science, LFCS'09.
    Dearfield Beach, Florida. 
    January 3, 2009.

    Download LFCS talk slides: PDF.       


Back to Sam Buss's publications page.