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

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

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.