Research Initiation: Counting Arguments and the Structure of Complexity Classes

研究启动：参数计数和复杂性类的结构

• 批准号: 8809174
• 负责人: Lane Hemaspaandra
• 金额: $ 1.78万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1988
• 资助国家: 美国
• 起止时间: 1988-07-01 至 1989-01-01
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8809174&HistoricalAwards=false
• 关键词: Research; Initiation; Counting; Arguments; Structure

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.

近年来，计数参数的使用已经开始产生关于复杂性类结构的结果。复杂性层次结构已经崩溃，新的类包含已经被发现。这个项目将使用计数参数来实现两个目标。首先，对立的计算范式——确定性、非确定性、唯一性、计数等。-将与发现新类内含物的目标和强（相对化）不可比较性结果进行比较。第二，将寻找缺乏完整语言的班级。这将增加基于字段计数的证明技术的工具箱，允许在各种类型的非完备性结果之间轻松转换。