The NP-completeness of reflected fragments of justification logics

TitleThe NP-completeness of reflected fragments of justification logics
Publication TypeConference Paper
Year of Publication2009
AuthorsBuss, SR, Kuznets, R
EditorArtemov, S, Nerode, A
Conference NameProceedings of Symposium on Logical Foundations of Computer Science (LFCS'09)
AbstractJustification 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.