This project will investigate the complexity of problems in logics. The focus will be on results that classify the complexity of an infinite number of problems. The first such result dates from 1978, when Schaefer proved his famous dichotomy theorem for generalized satisfiability problems. He defined an infinite number of propositional satisfiability problems (nowadays usually called Boolean constraint satisfaction problems), showed that all these satisfiability problems are either in P or NP-complete, and gave a simple criterion to determine which of the two cases holds. In recent years, quite a few dichotomy theorems have been shown about problems in logics. Almost all of these problems have the following three properties in common: They are variations of satisfiability, they are problems in propositional logic, and they use Schaefer's constraint framework.
This project's goal is to extend the existing research in three different directions, seeking dichotomy theorems for problems that are not related to satisfiability, for problems in logics other than propositional logic, and for frameworks other than Schaefer's constraint framework.
Broader Impacts:
Through her school's commitment to, as voluntary cost-sharing, reduce the proposer's teaching load by one course per year, and through the direct support of her summer months, this grant will have the broader impact of helping support research at an undergraduate institution. This harmonizes well with RIT's desire to become a more research-friendly institution. The travel support will allow the proposer and her students to attend conferences to develop professionally via learning of new advances, and presenting their results to the broader theory community.
