Tuesday, March 31, 20152:00 pmComputational Logic SeminarGraduate Center, 6421

NEXP-completeness and Universal Hardness Results for Justification Logic

Antonis Achilleos

Graduate Center CUNY

Antonis Achilleos

We provide a lower complexity bound for the satisfiability problem of a multi-agent justification logic, establishing that there are certain NEXP-complete multi-agent justification logics with interactions. We then use a simple modification of the corresponding reduction to prove that satisfiability for all multi-agent justification logics in a general class we consider is $Sigma_2^p$-hard — given certain reasonable conditions. Our methods improve on these required conditions for the same lower bound for the single-agent justification logics, proven by Buss and Kuznets in 2009, thus answering one of their open questions.

Link to paper on arXiv: