# NEXP-completeness and Universal Hardness Results for Justification Logic

arXiv: https://arxiv.org/abs/1503.00362 · HTML: https://mlsanity.com/paper/1503.00362/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2015.

## Built on by (most cited first, 2 of 2)

- [The Hardness of Reasoning about Probabilities and Causality](https://mlsanity.com/paper/2305.09508/) (2023)
- [Probabilistic and Causal Satisfiability: Constraining the Model](https://mlsanity.com/paper/2504.19944/) (2025)

## Abstract (arXiv)

We provide a lower complexity bound for the satisfiability problem of a multi-agent justification logic, establishing that the general NEXP upper bound from our previous work is tight. We then use a simple modification of the corresponding reduction to prove that satisfiability for all multi-agent justification logics from there is hard for the Sigma 2 p class of the second level of the polynomial hierarchy - 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.