Research Initiation: Investigations into the Structure of Intractable Sets

研究起始点：难解集结构研究

• 批准号: 8811996
• 负责人: John Geske
• 金额: $ 3.08万
• 依托单位: Michigan State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1988
• 资助国家: 美国
• 起止时间: 1988-09-01 至 1991-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8811996&HistoricalAwards=false
• 关键词: Research; Initiation; Investigations; into; Structure

This project is an investigation of the computational complexity of intractable sets. The object is to gain new insight into the rich mathematical structure that individual classes such as NP, EXP and TIME (2poly) appear to have, and to increase our understanding of the structural relationship between these classes. To these ends new concepts and proof techniques will be employed. Sets that are difficult to compute on almost all arguments play an important role in the structural analysis of complexity classes. Separation results between various deterministic, nondeterministic, and generalized Kolmogorov complexity classes can be witnessed by these sets. In cases where absolute results are elusive, relativization results will be achieved. Application of these results will be used to study the structure of complete sets in NP and EXP. A new nonconstructive reducibility that relates the polynomial complexity of computable sets will be used to investigate the structure of the classes NP and EXP. New results and insights into the fine structure of these classes have been obtained; further research into these areas is proposed.

这个项目是一个调查的计算复杂性， 难处理的集合 目的是对富人有新的认识 数学结构，单个类，如NP，EXP和TIME （2聚）似乎有，并增加我们的理解， 这些阶级之间的关系。 为此，新 将采用概念和证明技术。 几乎所有的参数都难以计算的集合， 在复杂性类的结构分析中起着重要作用。 各种确定性、非确定性和 广义Kolmogorov复杂性类可以由这些证明 集. 在绝对结果难以捉摸的情况下，相对化 将取得成果。 这些结果将用于研究的结构 NP和EXP中的完整集合。 一种新的非构造性约简， 可计算集合的多项式复杂度将用于 研究NP和EXP类的结构。 新成果及 已经获得了对这些类的精细结构的洞察; 建议对这些领域进行进一步研究。