A complexity question in justification logic
We examine the complexity of satisfiability for justification logic JD4. We prove completeness of this logic with respect to Fitting models of two states. Based on these semantics we give a tableau procedure for JD4. We conclude that satisfiability is in ? 2 p under reasonable conditions. We thus tighten the lower bound by Buss and Kuznets.
justification logic satisfiability computational complexity