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.

某些计算问题，例如图形连接性，匹配和原始测试允许时间效率的算法。另一方面，诸如布尔公式的问题，旅行推销员问题和货币等问题仍然无视这样的快速算法。 为什么自然计算问题之间存在这种计算差异？ 显然，这是一个基本问题，它影响了许多领域，包括数学，工程，经济学，优化和交流 - 计算机科学以外的领域。 “计算复杂性理论”的主要目标是研究有效的计算的概念。通常，效率是根据计算资源（例如时间和记忆（空间））来衡量的。该奖项将研究某些中心和长期存在的关于无确定性和随机性的中心和长期以来的问题，以记忆的计算上下文。确定性算法是无确定性计算的同时时间和空间的效率（c），以多次访问随机的磁带来调查计算的能力。拟议主题的研究将有助于理解计算的三个基本概念：确定性主义，非确定性，无确定性的计算，在计算中有限的综合性范围，这是在限制性上的范围。来自计算机科学以外的各个领域。该赠款的研究结果将在经过同行评审的期刊上发表，并将在国家和国际会议上介绍，从而使结果广泛传播以增强科学理解。将撰写针对更广泛的理论计算机科学受众的说明性调查文章。将根据该项目的主题创建和教授新课程，从而整合教学和研究。 该赠款还将用于各种人力资源开发活动，例如支持和指导研究生。