Randomness and Non-Determinism

随机性和非确定性

• 批准号: 0311411
• 负责人: Leonid Levin
• 金额: $ 25万
• 依托单位: Trustees of Boston University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-06-01 至 2007-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0311411&HistoricalAwards=false
• 关键词: Randomness; 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.

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