Complexity of Logics
逻辑的复杂性
基本信息
- 批准号:0311021
- 负责人:
- 金额:$ 9.99万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Continuing Grant
- 财政年份:2003
- 资助国家:美国
- 起止时间:2003-05-01 至 2007-04-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
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希望成为一个更有利于研究的机构的愿望相一致。 旅行支持将允许提议者和她的学生参加会议,通过学习新的进展来发展专业,并将他们的结果展示给更广泛的理论界。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Edith Hemaspaandra其他文献
Manipulation Complexity of Same-System Runoff Elections
- DOI:
10.1007/s10472-015-9490-6 - 发表时间:
2015-12-08 - 期刊:
- 影响因子:1.000
- 作者:
Zack Fitzsimmons;Edith Hemaspaandra;Lane A. Hemaspaandra - 通讯作者:
Lane A. Hemaspaandra
Isomorphic Implication
- DOI:
10.1007/s00224-007-9038-1 - 发表时间:
2007-09-14 - 期刊:
- 影响因子:0.400
- 作者:
Michael Bauland;Edith Hemaspaandra - 通讯作者:
Edith Hemaspaandra
All superlinear inverse schemes are coNP-hard
- DOI:
10.1016/j.tcs.2005.07.015 - 发表时间:
2005-11-22 - 期刊:
- 影响因子:
- 作者:
Edith Hemaspaandra;Lane A. Hemaspaandra;Harald Hempel - 通讯作者:
Harald Hempel
Correction to: Control in the presence of manipulators: cooperative and competitive cases
- DOI:
10.1007/s10458-020-09482-7 - 发表时间:
2020-10-12 - 期刊:
- 影响因子:2.600
- 作者:
Zack Fitzsimmons;Edith Hemaspaandra;Lane A. Hemaspaandra - 通讯作者:
Lane A. Hemaspaandra
Edith Hemaspaandra的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Edith Hemaspaandra', 18)}}的其他基金
ICES: Small: Collaborative Research: New Approaches to Computationally Protecting Elections from Manipulation
ICES:小型:协作研究:通过计算保护选举免遭操纵的新方法
- 批准号:
1101452 - 财政年份:2011
- 资助金额:
$ 9.99万 - 项目类别:
Standard Grant
U.S. - Germany Cooperative Research: Parallel Access to NP: Complexity and Applicability
美德合作研究:并行获取 NP:复杂性和适用性
- 批准号:
9815095 - 财政年份:1999
- 资助金额:
$ 9.99万 - 项目类别:
Standard Grant
相似海外基金
Border-artists: Critiquing border logics in transnational digital performance
边境艺术家:批判跨国数字表演中的边境逻辑
- 批准号:
2908114 - 财政年份:2023
- 资助金额:
$ 9.99万 - 项目类别:
Studentship
Integrating hybrid logics into concurrent program logic
将混合逻辑集成到并发程序逻辑中
- 批准号:
23K11051 - 财政年份:2023
- 资助金额:
$ 9.99万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Conference: Privileged Logics: Interrogating Foundations and Practices in Research Ethics
会议:特权逻辑:质疑研究伦理的基础和实践
- 批准号:
2316197 - 财政年份:2023
- 资助金额:
$ 9.99万 - 项目类别:
Standard Grant
SHF: Small: Little Tricky Logics: Misconceptions in Understanding Logics and Formal Properties
SHF:小:小棘手的逻辑:理解逻辑和形式属性的误解
- 批准号:
2227863 - 财政年份:2023
- 资助金额:
$ 9.99万 - 项目类别:
Standard Grant
CAREER: Designing Robust Cyber-Physical Systems: Logics, Automata, Optimization, and Heuristic Methods
职业:设计鲁棒的网络物理系统:逻辑、自动机、优化和启发式方法
- 批准号:
2240126 - 财政年份:2023
- 资助金额:
$ 9.99万 - 项目类别:
Continuing Grant
Fuzzy logics for graded reasoning in applied contexts
应用上下文中分级推理的模糊逻辑
- 批准号:
DE220100544 - 财政年份:2022
- 资助金额:
$ 9.99万 - 项目类别:
Discovery Early Career Researcher Award
Probing co-transcriptional gene regulatory logics in human transcriptomes
探索人类转录组中的共转录基因调控逻辑
- 批准号:
10674900 - 财政年份:2022
- 资助金额:
$ 9.99万 - 项目类别:
Strategy Logics for the Verification of Security Protocols
安全协议验证的策略逻辑
- 批准号:
EP/V009214/1 - 财政年份:2021
- 资助金额:
$ 9.99万 - 项目类别:
Research Grant
Collaborative Research: CPS: Medium: Spatio-Temporal Logics for Analyzing and Querying Perception Systems
合作研究:CPS:媒介:用于分析和查询感知系统的时空逻辑
- 批准号:
2039087 - 财政年份:2021
- 资助金额:
$ 9.99万 - 项目类别:
Standard Grant
Collaborative Research: CPS: Medium: Spatio-Temporal Logics for Analyzing and Querying Perception Systems
合作研究:CPS:媒介:用于分析和查询感知系统的时空逻辑
- 批准号:
2038666 - 财政年份:2021
- 资助金额:
$ 9.99万 - 项目类别:
Standard Grant