Randomness and Non-Determinism

点击翻译按钮获取中文摘要

This project will investigate the complexity of problems in logics.The focus will be on results that classify the complexity of aninfinite number of problems. The first such result dates from 1978,when Schaefer proved his famous dichotomy theorem for generalizedsatisfiability problems. He defined an infinite number of propositionalsatisfiability problems (nowadays usually called Boolean constraintsatisfaction problems), showed that all these satisfiability problems areeither in P or NP-complete, and gave a simple criterion to determinewhich of the two cases holds. In recent years, quite a few dichotomytheorems have been shown about problems in logics. Almost all ofthese problems have the following three properties in common: Theyare 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 threedifferent directions, seeking dichotomy theorems for problems thatare not related to satisfiability, for problems in logics other thanpropositional logic, and for frameworks other than Schaefer'sconstraint 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 supportresearch at an undergraduate institution. This harmonizeswell with RIT's desire to become a more research-friendlyinstitution. The travel support will allow the proposer andher students to attend conferences to develop professionallyvia learning of new advances, and presenting their results tothe broader theory community.