Some Problems in Complexity Theory

复杂性理论中的一些问题

• 批准号: 0511679
• 负责人: Jin-Yi Cai
• 金额: $ 20万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-01 至 2009-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0511679&HistoricalAwards=false
• 关键词: Some; Problems; Complexity; Theory

This project is a study of some problems in computational complexity theory, in particularsome problems in structural complexity theory, and a number of algorithmic problems related to graph isomorphism.In graph isomorphism, the investigator proposes to study further notions of coloring schemes, and in particular how such coloring schemes relate to graph spectra. We also wish to study a number of structural complexity theoretic questions as related to graph isomorphism and graph automorphism. It is expected that techniques of group theory, linear algebra, and combinatorics will interact in this study. The PI in collaboration with Prof. Osamu Watanabe have proposed a notion of stringent relativization, which is a generalization of the Karp-Lipton notion of advice strings. This study is related to circuit complexity theory and techniques of derandomization and algebraic techniques. We would like to develop this notion further. The investigator also proposes to study further a notion of persistent NP-hardness. We envision this to be an intermediate level of complexity measure between worst-case hardness and average-case complexity in the framework of Levin and others.

本课题研究了计算复杂性理论中的一些问题，特别是结构复杂性理论中的一些问题，以及一些与图同构有关的算法问题。在图同构中，研究者建议进一步研究着色方案的概念，特别是这种着色方案与图的谱之间的关系。我们还希望研究与图同构和图自同构相关的一些结构复杂性理论问题。预计群论、线性代数和组合学的技术将在这项研究中相互作用。PI与渡边修教授合作提出了严格相对化的概念，这是卡普-利普顿关于建议字符串的概念的推广。本研究涉及电路复杂性理论、去随机化技术和代数技术。我们希望进一步发展这一概念。研究者还建议进一步研究持久NP难的概念。在Levin和其他人的框架中，我们设想这是介于最坏情况复杂性和平均情况复杂性之间的中间复杂性水平。