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.
