AF:Small:RUI:Concrete Computational Complexity

AF:小:RUI:具体计算复杂度

• 批准号: 0917026
• 负责人: Nicholas Pippenger
• 金额: $ 12.21万
• 依托单位: Harvey Mudd College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0917026&HistoricalAwards=false
• 关键词: AF; Small; RUI; Concrete; Computational

The goal of computational complexity theory is to determine the computational resources needed to carry out various computational tasks. The resources measured may involve hardware (such as gates used to construct a circuit, or area on a chip) or software (such as the time or space used in the execution of a program on a machine), and the tasks considered may range from simple addition of two integers to a large algebraic or geometric computation.This project will deal primarily with "low level" complexity theory, in which the resources required grow modestly (at most quadratically) with the size of the task. Examples of such tasks are furnished by the arithmetic operations (addition, subtraction, multiplication, division and square-root extraction) performed by the executions of single instructions in a computer. For these tasks, hardware-oriented resource measures are most appropriate in most cases.The broader impacts of the project lie in the opportunity it will provide to explore a new model for undergraduate research. The most common model for undergraduate research is to give students problems that they may reasonably be expected to solve within the time allowed (typically an academic year for a senior thesis, or ten weeks for a summer assignment). This project will explore a new model, wherein students are assigned the task of working on an authentic research problem (one that has resisted solution for many years, and is unlikely to be resolved with a single new stroke), with the goal of making a contribution (even a small one) that might play a role in an eventual resolution. If explored with imagination, this new model should provide a valuable complement to the established practices for undergraduate research.

计算复杂性理论的目的是确定执行各种计算任务所需的计算资源。测得的资源可能涉及硬件（例如用于构建电路的门，或软件）（例如在机器上执行程序执行的时间或空间），并且所考虑的任务范围从简单添加两个整数从大型代数或几何计算中，这些项目将主要与“低级别”相关的“低级别”，“低级别”的规模是，大多数的复杂性是“ Quigent”的规模。 任务。此类任务的示例由算术操作（加法，减法，乘法，除法和平方根提取）通过计算机中的单个指令执行执行。 对于这些任务，在大多数情况下，面向硬件的资源指标最合适。该项目的更广泛的影响在于它将为探索本科研究的新模型提供的机会。本科研究的最常见模型是为学生提供可能在允许的时间内合理地解决的问题（通常是高级论文的学年，或夏季任务的十个星期）。 该项目将探索一种新模型，其中将学生分配了解决真实研究问题的任务（该问题已经抵抗了多年的解决方案，并且不太可能通过单个新的中风解决），目的是为最终解决方案中的贡献（甚至是一个小）贡献（甚至是一个小）。如果有想象力探索，这种新模型应为既定的本科研究实践提供宝贵的补充。