### 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

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.