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

AF：小型：协作研究：探索空间有限计算的新方法

• 批准号: 1422668
• 负责人: Vinodchandran Variyam
• 金额: $ 24.61万
• 依托单位: University of Nebraska-Lincoln
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1422668&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Exploring

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.

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