AF:Small:RUI:Concrete Computational Complexity

计算复杂性理论的目标是确定执行各种计算任务所需的计算资源。测量的资源可能涉及硬件（如用于构建电路的门，或芯片上的区域）或软件（如在机器上执行程序所用的时间或空间），而所考虑的任务范围可能从两个整数的简单相加到大型代数或几何计算。本项目将主要处理“低层次”复杂性理论，其中所需的资源随着任务的大小适度增长（最多是二次方）。此类任务的示例由计算机中执行单个指令所执行的算术运算（加、减、乘、除和平方根提取）提供。 对于这些任务，硬件为导向的资源措施在大多数情况下是最合适的。该项目的更广泛的影响在于它将提供探索本科生研究新模式的机会。本科研究最常见的模式是给学生一些问题，他们可能会合理地期望在允许的时间内解决（通常是一学年的毕业论文，或十周的夏季作业）。 该项目将探索一种新的模式，其中学生被分配到一个真实的研究问题（多年来一直抵制解决方案，并且不太可能通过一个新的中风来解决）的工作任务，其目标是做出贡献（即使是一个小的），这可能会在最终的解决方案中发挥作用。如果探索与想象力，这种新的模式应该提供了一个有价值的补充，以建立本科研究的做法。

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.