Structural Complexity Theory

结构复杂性理论

基本信息

  • 批准号:
    9322513
  • 负责人:
  • 金额:
    $ 15.93万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Continuing Grant
  • 财政年份:
    1994
  • 资助国家:
    美国
  • 起止时间:
    1994-09-01 至 1998-08-31
  • 项目状态:
    已结题

项目摘要

The structure of feasible computations determines whether one can efficiently solve the optimization problems posed by nature and the modern world. The long-term goal of this research is to understand which problems have efficient solutions, via learning why certain problems may lack computationally feasible algorithms. Of particular interest are the structural relationships between complexity classes, and the internal structure of complexity classes. Though the project intends to broadly investigate this area, focus will be given to the research via two themes: (a) dealing with unpredictable execution order; and (b) the properties of sparse sets. On the first topic, this project investigates the class of languages computable via a large number of short subtasks, each of which is given the (small) result of the subtask that executed before it. This has been studied by Cai and Furst and others for the case where the scheduling of the subtasks is trivial and fixed. However, the project studies the case in which the order in which the subtasks execute is unpredictable. On the second topic, several issues dealing with sparse sets (which are a classic examples of `sets of low information content`) are examined.
可行计算的结构决定了一个人是否 可以有效地解决自然界和自然界提出的优化问题, 现代世界 这项研究的长期目标是了解哪些问题有有效的解决方案,通过学习为什么某些问题可能缺乏计算上可行的算法。 特别感兴趣的是复杂性类之间的结构关系,以及复杂性类的内部结构。 虽然该项目打算广泛调查这一领域,重点将通过两个主题的研究:(a)处理不可预测的执行顺序;(B)稀疏集的属性。 在第一个主题中,该项目研究了通过大量短子任务可计算的语言类,每个子任务都给出了在它之前执行的子任务的(小)结果。Cai和Furst等人已经研究了子任务的调度是平凡和固定的情况。 然而,该项目研究的情况下,其中的子任务执行的顺序是不可预测的。 关于第二个议题, 研究了处理稀疏集合(这是“低信息量集合”的典型例子)的几个问题。

项目成果

期刊论文数量(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
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Standard Grant
AF: Small: Complexity and Computational Social Choice
AF:小:复杂性和计算社会选择
  • 批准号:
    2006496
  • 财政年份:
    2020
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Standard Grant
ICES: Small: Collaborative Research: New Approaches to Computationally Protecting Elections from Manipulation
ICES:小型:协作研究:通过计算保护选举免遭操纵的新方法
  • 批准号:
    1101479
  • 财政年份:
    2011
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Standard Grant
RI:HCC:Small:Preference Aggregation: Bypassing Worst-Case Protections
RI:HCC:Small:偏好聚合:绕过最坏情况保护
  • 批准号:
    0915792
  • 财政年份:
    2009
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Standard Grant
ITR - (ECS+ASE+NHS) - (dmc): Richer Understanding of the Complexity of Election Systems
ITR - (ECS ASE NHS) - (dmc):对选举系统复杂性的更深入了解
  • 批准号:
    0426761
  • 财政年份:
    2004
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Continuing Grant
U.S.-Germany Cooperative Research on Structure in ComplexityTheory
美德复杂性理论结构合作研究
  • 批准号:
    9513368
  • 财政年份:
    1996
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Standard Grant
U.S.-Japan Cooperative Research: Counting Classes, Closure Properties, and Hash Functions
美日合作研究:类计数、闭包性质和哈希函数
  • 批准号:
    9116781
  • 财政年份:
    1992
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Standard Grant
PYI: Structural Complexity Theory
PYI:结构复杂性理论
  • 批准号:
    8957604
  • 财政年份:
    1989
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Continuing Grant
Research Initiation: Counting Arguments and the Structure of Complexity Classes
研究启动:参数计数和复杂性类的结构
  • 批准号:
    8996198
  • 财政年份:
    1989
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Standard Grant
Research Initiation: Counting Arguments and the Structure of Complexity Classes
研究启动:参数计数和复杂性类的结构
  • 批准号:
    8809174
  • 财政年份:
    1988
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Standard Grant

相似海外基金

CAREER: Complexity Theory of Quantum States: A Novel Approach for Characterizing Quantum Computer Science
职业:量子态复杂性理论:表征量子计算机科学的新方法
  • 批准号:
    2339116
  • 财政年份:
    2024
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Continuing Grant
Conference: Tensor Invariants in Geometry and Complexity Theory
会议:几何和复杂性理论中的张量不变量
  • 批准号:
    2344680
  • 财政年份:
    2024
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Standard Grant
Algebraic complexity theory via the algebraic geometry and representation theory of generalised continued fractions
通过代数几何和广义连分数表示论的代数复杂性理论
  • 批准号:
    EP/W014882/2
  • 财政年份:
    2023
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Research Grant
Non-regular complexity theory
非正则复杂性理论
  • 批准号:
    23K10976
  • 财政年份:
    2023
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
NSF-BSF: New Approaches to Conformal Field Theory - Codes, Ensembles, and Complexity
NSF-BSF:共形场论的新方法 - 代码、系综和复杂性
  • 批准号:
    2310426
  • 财政年份:
    2023
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Continuing Grant
Representation Theory Meets Computational Algebra and Complexity Theory
表示论遇见计算代数和复杂性理论
  • 批准号:
    2302375
  • 财政年份:
    2023
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Standard Grant
Towards a Unified Theory of Proof and Circuit Complexity
走向证明和电路复杂性的统一理论
  • 批准号:
    RGPIN-2021-03036
  • 财政年份:
    2022
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Discovery Grants Program - Individual
Towards a Unified Theory of Proof and Circuit Complexity
走向证明和电路复杂性的统一理论
  • 批准号:
    RGPAS-2021-00032
  • 财政年份:
    2022
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Discovery Grants Program - Accelerator Supplements
SHF: Small: Data Movement Complexity: Theory and Optimization
SHF:小型:数据移动复杂性:理论与优化
  • 批准号:
    2217395
  • 财政年份:
    2022
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Standard Grant
Optimization, Complexity, Algebra and Invariant Theory
最优化、复杂性、代数和不变理论
  • 批准号:
    RGPIN-2020-04599
  • 财政年份:
    2022
  • 资助金额:
    $ 15.93万
  • 项目类别:
    Discovery Grants Program - Individual
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了