EXPSPACE-Completeness of the Logics K4xS5 and S4xS5 and the Logic of Subset Spaces, Part 2: EXPSPACE-Hardness

2019/08/09 by Peter Hertling, Hertling, Peter, Gisela Krommes +1
Computer Science · #03B45 #68Q17 #68Q25 #Advanced Algebra and Logic #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #Rough Sets and Fuzzy Logic

paper · pdf · doi:10.48550/arxiv.1908.03509

openalex publication_date 2019/08/09 · openalex created_date 2019/08/22 · openalex updated_date 2026/07/28

Abstract

It is known that the satisfiability problems of the product logics K4xS5 and S4xS5 are NEXPTIME-hard and that the satisfiability problem of the logic SSL of subset spaces is PSPACE-hard. We improve these lower bounds for the complexity of these problems by showing that all three problems are EXPSPACE-hard under logspace reduction. In another paper we show that these problems are in ESPACE. This shows that all three problems are EXPSPACE-complete.

Related

• EXPSPACE-Completeness of the Logics K4xS5 and S4xS5 and the Logic of\n Subset Spaces, Part 1: ESPACE-Algorithms
• Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic
• The Complexity of Satisfiability for Sub-Boolean Fragments of ALC
• Logics with the axiom of convergence: complexity with a small number of variables in the language (extended version)
• Characterizing the Exponential-Space Hierarchy Via Partial Fixpoints