Complexity of Logics

这个项目将调查逻辑问题的复杂性。重点将放在对无限数量的问题的复杂性进行分类的结果上。第一个这样的结果可以追溯到1978年，当时Schaefer证明了他关于广义可满足性问题的著名的二分法定理。他定义了无穷多个命题可满足性问题(现在通常称为布尔约束满足性问题)，证明了所有这些可满足性问题要么是P完全的，要么是NP完全的，并给出了一个简单的准则来判断这两种情况中哪种情况成立。近年来，关于逻辑学中的问题，出现了不少二分性定理。几乎所有这些问题都有以下三个共同的性质：它们是可满足性的变体，它们是命题逻辑中的问题，并且它们使用了Schaefer的约束框架。本项目的目标是在三个不同的方向上扩展现有的研究，为与可满足性无关的问题寻找二分法定理，为非命题逻辑中的问题寻找二分法定理，以及为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.