Concrete Problems in Computational Complexity Theory

计算复杂性理论中的具体问题Nicholas Pippenger普林斯顿大学计算机科学系计算复杂性理论的目标是确定执行各种计算任务所需的计算资源。所测量的资源可能涉及硬件（如用于构建电路的门，或芯片上的区域）或软件（如在机器上执行程序所用的时间或空间），所考虑的任务可能从两个整数的简单相加到大型代数或几何计算。拟议的研究将主要处理“低水平”复杂性理论，其中所需的资源随着任务的大小适度增长（最多是二次方）。这类任务的例子是通过在计算机中执行单个指令而完成的算术运算（加、减、乘、除和平方根提取）。对于这些任务，面向硬件的资源措施在大多数情况下是最合适的。拟议的研究也将探讨涉及容错计算的问题。有一个关于电路中瞬态误差的经典理论，它相当清楚地描述了这种情况下的理论可能性和局限性。拟议的研究将涉及容错计算的两个方面，其中所知甚少：随着时间的推移发生的永久性错误，以及量子通信和计算中的瞬时错误。对于这些问题，面向硬件的资源措施再次是最合适的。拟议的研究的更广泛的影响在于促进理论计算机科学与数学和物理学之间的跨学科联系。当然，计算机科学家一直都在大量利用数学和物理的技术和结果，因为数学和物理是计算机科学和工程的基础。然而，这里提出的是通过将理论计算机科学中开发的方法应用于数学家和物理学家感兴趣的问题来回报这种青睐。

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.