2015/03/01 by Antonis Achilleos, Achilleos, Antonis · 1 citation
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Multi-Agent Systems and Negotiation #cs.CC #cs.LO
paper · pdf · doi:10.48550/arxiv.1503.00362
Shorter version has been accepted for publication by CSR 2015
arxiv created 2015/03/01 · openalex publication_date 2015/03/01 · arxiv updated 2015/03/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.