AF: Small: Collaborative Research:Exploring New Approaches in Space Bounded Computation

某些计算问题，如图的连通性、匹配性和素性测试，允许使用时间效率高的算法。另一方面，布尔公式可满足性、旅行商问题和因式分解等问题仍然不能满足这种快速算法。为什么在自然的计算问题中会存在这样的计算差异？这显然是一个影响许多领域的基础性问题，包括数学、工程、经济学、优化和通信--这些领域超出了计算机科学的范畴。“计算复杂性理论”的主要目的是研究有效计算的概念。通常，效率是根据时间和内存(空间)等计算资源来衡量的。该奖项将调查某些中心和长期悬而未决的问题，这些问题涉及内存高效计算中的不确定性和随机性。通过对内存受限计算的研究，它将(A)研究无二义性在非确定性计算中的作用(B)设计对非确定性计算同时具有时间和空间效率的确定性算法(C)研究多次访问随机磁带的计算的能力。对所提出的主题的研究将有助于在有限内存计算的背景下理解计算的三个基本概念之间的关系：确定性、非确定性和随机性。从这个项目中获得的直觉将加深我们对解决计算机科学以外各个领域的实际计算问题的复杂性的理解。这笔赠款的研究成果将发表在同行评议的期刊上，并将在国家和国际会议上发表，从而使结果得以广泛传播，以增进科学理解。将撰写面向更广泛的理论计算机科学受众的说明性调查文章。将围绕该项目的主题创建和教授新课程，从而将教学和研究结合在一起。这笔赠款还将用于各种人力资源开发活动，如支持和指导研究生。

Certain computational problems such as graph connectivity, matching, and primality testing admit time-efficient algorithms. On the other hand problems such as boolean formula satisfiability, traveling salesman problem, and factoring still defy such fast algorithms. Why does such computational disparity exist among natural computational problems? This clearly is a foundational question which impacts many areas including mathematics, engineering, economics, optimization, and communication - areas beyond computer science. The main goal of "computational complexity theory'' is to study the notion of efficient computation. Typically, efficiency is measured in terms of computational resources such as time and memory (space).This award will investigate certain central and longstanding open questions concerning nondeterminism and randomness in the context of memory-efficient computations. By focusing on memory-bounded computations, it will (a) study the role of unambiguity in nondeterminism (b) design deterministic algorithms that are simultaneously time and space efficient for nondeterministic computations (c) investigate the power of computations with multiple access to a random tape.Study of proposed topics will help in understanding relations among three fundamental concepts of computation: determinism, nondeterminism and randomness, in the context of computations with limited memory. Intuition gained from this project will enhance our understanding of the complexity of solving practical computational problems arising from various fields beyond computer science. Research results from this grant will be published in peer-reviewed journals and will be presented at national and international conferences, thus enabling broad dissemination of the results to enhance scientific understanding. Expository survey articles aimed at a broader theoretical computer science audience will be written. New courses will be created and taught along the theme of this project, thus integrating teaching and research. The grant will also be used for various human resource development activities such as supporting and mentoring graduate students.