NEXP-completeness and Universal Hardness Results for Justification Logic

Computational Logic SeminarTuesday, March 31, 20152:00 pmGraduate Center, 6421

Antonis Achilleos

NEXP-completeness and Universal Hardness Results for Justification Logic

Graduate Center CUNY

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:
http://arxiv.org/abs/1503.00362

Posted by on March 25th, 2015