Title: Generalized Modal Satisfiability
Speaker: Henning Schnoor, University of Hanover
Date: October 4, 2005 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
It is well-known that modal satisfiability is PSPACE-complete (Ladner 1977). However, the complexity may decrease if we restrict the set of propositional operators used.
We completely classify the complexity of modal satisfiability for every finite set of propositional operators, i.e., we classify an infinite number of problems.
We show that, depending on the set of propositional operators, modal satisfiability is PSPACE-complete, coNP-complete, or in P.
Joint work with Edith Hemaspaandra.