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.