DIMACS Theoretical Computer Science Seminar

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


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.