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.

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