Computational Logic SeminarTuesday, March 31, 20152:00 pmGraduate Center, 6421
NEXP-completeness and Universal Hardness Results for Justification Logic
Antonis Achilleos
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