Concrete Problems in Computational Complexity Theory

点击翻译按钮获取中文摘要

Concrete Problems in Computational Complexity TheoryNicholas PippengerDepartment of Computer SciencePrinceton UniversityThe 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 a simple addition of two integers to a large algebraic or geometric computation.The proposed research 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, divisionand square-root extraction) performed by the execution of single instructions in a computer. For these tasks, hardware-oriented resource measures are most appropriate in most cases.The proposed research will also explore problems involving fault-tolerant computing. There is a classical theory concerning transient errors in circuits that delineates fairly clearly the theoretical possibilities and limitations in this situation. The proposed research will deal with two aspects of fault-tolerant computing about which much less is known:permanent errors occurring over time, and transient errors in quantum communication and computation. For these questions, hardware-oriented resource measures are again most appropriate.The broader impacts of the proposed research lie in the promotion of interdisciplinary links between theoretical computer science on one hand, and mathematics and physics on the other. It has of course always been the case that computer scientists have drawn heavily on techniques and results from mathematics and physics, since mathematics and physics form the foundations of computer science and engineering. What is proposed here, however, is to return the favor by applying methods developed within theoretical computer science to problems of interest to mathematicians and physicists.