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）研究对随机磁带的多路访问的计算能力。研究建议的主题将有助于理解计算的三个基本概念之间的关系：确定性，非确定性和随机性，在有限内存的计算环境中。从这个项目中获得的直觉将增强我们对解决计算机科学以外的各个领域所产生的实际计算问题的复杂性的理解。这项赠款的研究成果将发表在同行评审的期刊上，并将在国家和国际会议上发表，从而使研究结果得到广泛传播，以提高科学认识。将撰写针对更广泛的理论计算机科学受众的解释性调查文章。新的课程将沿着这个项目的主题创建和教授，从而将教学和研究结合起来。 这笔赠款还将用于各种人力资源开发活动，如支持和指导研究生。