Structural Computational Complexity

本研究的战略目标是促进计算复杂性综合理论的发展。计算复杂性是对控制计算的定量规律的研究，它是指导、利用和开发爆炸式增长的计算机技术所需的科学基础的重要组成部分。提出的研究有两个主要目标：a)更好地理解是什么使问题难以计算，并开发技术来验证硬度，b)探索利用不足以解决问题的计算资源可以做的最好的事情。计算复杂性根据解决问题所需的各种计算资源的数量对问题进行分类。这种分类产生的复杂性类包含在给定计算资源范围内可以解决的所有问题。为了更深入地理解是什么使问题难以计算，该项目探索了各种复杂性类、这些类之间的关系以及这些类的内部结构。它还探讨了在解决问题时不同计算资源之间的权衡，特别关注顺序时间、并行时间、不确定性时间、内存需求、作为计算资源的随机性和交互式计算。

The strategic goal of this research is to contribute to the development of a comprehensive theory of computational complexity. Computational complexity is the study of the quantitative laws that govern computation and it is an essential part of the science base needed to guide, harness and exploit the explosively growing computer technology. The proposed research has two main goals: a) to understand better what makes problems hard to compute and to develop techniques to verify the degree of hardness, b) to explore what is the best that can be done with computational resources not sufficient to solve a problem. Computational complexity classifies problems by the amounts of various computational resources needed to solve them. This classification yields complexity classes that consist of all problems that can be solved within a given computational resource bound. To gain a deeper understanding of what makes problems hard to compute, the project explores various complexity classes, relations between these classes and the internal structure of these classes. It also explores the trade-offs between different computational resources in problem solving, with particular attention to sequential-time, parallel-time, nondeterministic-time, memory requirements, randomness as a computational resource and interactive computing.