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.

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