AF: Small: Collaborative Research: Studies in Nonuniformity, Completeness, and Reachability

AF：小型：协作研究：非均匀性、完整性和可达性的研究

• 批准号: 0916525
• 负责人: Vinodchandran Variyam
• 金额: $ 27.2万
• 依托单位: University of Nebraska-Lincoln
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-15 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0916525&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Studies

Computational complexity theory classifies computational problems into various complexity classes based on the amount of resources needed to solve them. This classification is done by measuring various resources such as time, space, nonuniformity, nondeterminism, and randomness. A better understanding of the relationships among these various resources shed light on the computational difficulty of the problems that are encountered in practice. This project explores several central questions regarding nonuniformity, complete problems, and space bounded computations. This project attempts to discover improved upper bounds for problems with high circuit complexity. Regarding complete sets, non-relativizing properties of complete sets will be explored. Space bounded computations will be investigated in the context of planar graph reachability problems. This project addresses several basic questions in computational complexity theory. The results from this project will further our understanding of computational resources such as nonuniformity, nondeterminism, and space. Research results will be published in peer-reviewed journals and will be presented at national and international conferences, thus enabling broad dissemination of the the results to enhance scientific understanding. New courses will be created and taught along the themes of this project, thus integrating teaching and research. The project supports various human resource development activities such as supporting and mentoring graduate students and inviting visitors.

计算复杂性理论将计算问题根据解决它们所需的资源量分为各种复杂性类别。这种分类是通过测量各种资源，如时间，空间，非均匀性，非确定性和随机性来完成的。更好地理解这些不同的资源之间的关系，揭示了在实践中遇到的问题的计算难度。这个项目探讨了几个关于不均匀性，完整的问题，和空间有界计算的中心问题。这个项目试图发现高电路复杂性问题的改进上限。关于完整集合，将探讨完整集合的非相对化属性。空间有界计算将在平面图可达性问题的背景下进行研究。这个项目解决了计算复杂性理论中的几个基本问题。这个项目的结果将进一步加深我们对计算资源的理解，如非均匀性，非确定性和空间。研究结果将发表在同行评审的期刊上，并将在国家和国际会议上介绍，从而使研究结果得到广泛传播，以提高科学认识。新课程将沿着这个项目的主题创建和教授，从而将教学和研究结合起来。该项目支持各种人力资源开发活动，如支持和指导研究生以及邀请来访者。