Complexity of Logics

这个项目将研究逻辑问题的复杂性。重点将放在对无数问题的复杂性进行分类的结果上。第一个这样的结果可以追溯到1978年，当时Schaefer证明了他著名的关于广义可满足性问题的二分定理。他定义了无数的命题可满足性问题（现在通常称为布尔约束满足问题），证明了所有这些可满足性问题要么是P完全的，要么是np完全的，并给出了一个简单的准则来确定这两种情况中的哪一种成立。近年来，在逻辑问题中出现了不少二分类定理。几乎所有这些问题都有以下三个共同的性质：它们是可满足性的变化，它们是命题逻辑中的问题，它们使用谢弗的约束框架。这个项目的目标是在三个不同的方向上扩展现有的研究，寻找与可满足性无关的问题的二分定理，命题逻辑以外的逻辑问题，以及Schaefer约束框架以外的框架。更广泛的影响：通过她的学校承诺，作为自愿的成本分摊，每年减少申请人的教学负担一门课程，并通过对她夏季月份的直接支持，这项资助将对帮助支持本科机构的研究产生更广泛的影响。这与RIT希望成为一个更友好的研究机构的愿望很好地协调一致。旅行支持将允许申请人和她的学生参加会议，通过学习新的进展来发展专业，并向更广泛的理论界展示他们的成果。

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.