Research Initiation: Counting Arguments and the Structure of Complexity Classes
研究启动:参数计数和复杂性类的结构
基本信息
- 批准号:8809174
- 负责人:
- 金额:$ 1.78万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:1988
- 资助国家:美国
- 起止时间:1988-07-01 至 1989-01-01
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
In recent years the use of counting arguments has begun to yield results about the structure of complexity classes. Complexity hierarchies have collapsed and new class inclusions have been discovered. This project will use counting arguments to achieve two goals. First, the rival computational paradigms - deterministic, nondeterministic, unique, counting,etc. - will be compared with the goal of discovering new class inclusions and strong (relativized) incomparability results. Second, classes lacking complete languages will be sought. This will add to the tool kit of the field counting based proof techniques that allow easy conversion between various types of non-completeness results.
近年来,计数参数的使用已经开始产生有关复杂性类结构的结果。 复杂性的层次结构已经崩溃,新的类包含物也被发现了。 该项目将使用计数参数来实现两个目标。 首先,竞争的计算范式——确定性、非确定性、唯一性、计数等。 - 将与发现新类包含物和强(相对化)不可比性结果的目标进行比较。 其次,将寻找缺乏完整语言的课程。 这将添加到基于字段计数的证明技术的工具包中,从而允许在各种类型的不完整性结果之间轻松转换。
项目成果
期刊论文数量(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 }}
Lane Hemaspaandra其他文献
Lane Hemaspaandra的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Lane Hemaspaandra', 18)}}的其他基金
Collaborative Research: Improving Student Learning Outcomes in Computer Science Theory Courses Using Conceptual Models
协作研究:使用概念模型提高计算机科学理论课程中学生的学习成果
- 批准号:
2135431 - 财政年份:2022
- 资助金额:
$ 1.78万 - 项目类别:
Standard Grant
AF: Small: Complexity and Computational Social Choice
AF:小:复杂性和计算社会选择
- 批准号:
2006496 - 财政年份:2020
- 资助金额:
$ 1.78万 - 项目类别:
Standard Grant
ICES: Small: Collaborative Research: New Approaches to Computationally Protecting Elections from Manipulation
ICES:小型:协作研究:通过计算保护选举免遭操纵的新方法
- 批准号:
1101479 - 财政年份:2011
- 资助金额:
$ 1.78万 - 项目类别:
Standard Grant
RI:HCC:Small:Preference Aggregation: Bypassing Worst-Case Protections
RI:HCC:Small:偏好聚合:绕过最坏情况保护
- 批准号:
0915792 - 财政年份:2009
- 资助金额:
$ 1.78万 - 项目类别:
Standard Grant
ITR - (ECS+ASE+NHS) - (dmc): Richer Understanding of the Complexity of Election Systems
ITR - (ECS ASE NHS) - (dmc):对选举系统复杂性的更深入了解
- 批准号:
0426761 - 财政年份:2004
- 资助金额:
$ 1.78万 - 项目类别:
Continuing Grant
U.S.-Germany Cooperative Research on Structure in ComplexityTheory
美德复杂性理论结构合作研究
- 批准号:
9513368 - 财政年份:1996
- 资助金额:
$ 1.78万 - 项目类别:
Standard Grant
U.S.-Japan Cooperative Research: Counting Classes, Closure Properties, and Hash Functions
美日合作研究:类计数、闭包性质和哈希函数
- 批准号:
9116781 - 财政年份:1992
- 资助金额:
$ 1.78万 - 项目类别:
Standard Grant
Research Initiation: Counting Arguments and the Structure of Complexity Classes
研究启动:参数计数和复杂性类的结构
- 批准号:
8996198 - 财政年份:1989
- 资助金额:
$ 1.78万 - 项目类别:
Standard Grant
相似国自然基金
星形胶质细胞糖代谢重编程介导Lactoferrin基因缺失引发的早期生长迟缓和认知障碍
- 批准号:32371037
- 批准年份:2023
- 资助金额:50 万元
- 项目类别:面上项目
局域结构引发Pr3+高偏振度荧光发射的研究
- 批准号:12304449
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
线粒体tRNA修饰酶GTPBP3基因突变引发肥厚型心肌病的机理研究
- 批准号:32300482
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
基于α-氨基酮衍生物的高效生物相容性光聚合引发体系的构建及其机理研究
- 批准号:22361019
- 批准年份:2023
- 资助金额:33 万元
- 项目类别:地区科学基金项目
基于光引发点击化学的整体柱制备及在血脑屏障芯片评价益智仁黄酮类成分跨膜转运中的应用
- 批准号:82360707
- 批准年份:2023
- 资助金额:31 万元
- 项目类别:地区科学基金项目
相似海外基金
Defining the cytoplasmic sequestration of Caenorhabditis elegans orphan nuclear receptor 49 on trafficking vesicles
定义秀丽隐杆线虫孤儿核受体 49 在运输囊泡上的细胞质隔离
- 批准号:
10674775 - 财政年份:2021
- 资助金额:
$ 1.78万 - 项目类别:
Single-photon counting APD arrays for high-through-put single-molecule assays
用于高通量单分子检测的单光子计数 APD 阵列
- 批准号:
8814242 - 财政年份:2012
- 资助金额:
$ 1.78万 - 项目类别:
Single-photon counting APD arrays for high-through-put single-molecule assays
用于高通量单分子检测的单光子计数 APD 阵列
- 批准号:
8297138 - 财政年份:2012
- 资助金额:
$ 1.78万 - 项目类别:
Single-photon counting APD arrays for high-through-put single-molecule assays
用于高通量单分子检测的单光子计数 APD 阵列
- 批准号:
8464158 - 财政年份:2012
- 资助金额:
$ 1.78万 - 项目类别:
Research Initiation: Counting Arguments and the Structure of Complexity Classes
研究启动:参数计数和复杂性类的结构
- 批准号:
8996198 - 财政年份:1989
- 资助金额:
$ 1.78万 - 项目类别:
Standard Grant