TR-2014003: On the Complexity of Two-Agent Justification Logic
Antonis Achilleos · CUNY Academic Works (City University of New York) · 2014
We investigate the complexity of derivability for two-agent Justification Logic.For this purpose we revisit Yavorskaya's two-agent LP with interactions (2008), we simplify the syntax and provide natural extensions.We consider two-agent versions of other justification logics as well as ways to combine two justification logics.For most of these cases we prove that the upper complexity bound established for the single-agent cases are maintained: these logics' derivability problem is in the second step of the polynomial hierarchy.For certain logics, though, we discover a complexity jump to PSPACE-completeness, which is a new phenomenon for Justification Logic.