Complexity of Feasible Computations

9400229塞尔曼这项工作将继续对可行计算的计算复杂性进行研究。其目的是区分包含可行计算的复杂类和不包含可行计算的复杂类的性质，揭示单个复杂类(如NP)似乎具有的丰富结构，并增加对低级别复杂类之间的结构关系的理解。重点将是继续研究多值计算的复杂性以及非一致和一致复杂性之间的关系。这种方法是结构复杂性的标准范例，即引出复杂类的结构属性，而不是分析个别的具体问题。***

9400229 Selman This work will continue the research effort on the computational complexity of feasible computations. The objective is to distinguish properties of complexity classes that contain feasible computations from those that do not, to reveal the rich structure that individual complexity classes, such as NP, appear to have, and to increase understanding of the structural relations between low-level complexity classes. The emphasis will be to continue research on the complexity of multivalued computations and on relations between nonuniform and uniform complexity. The approach is the standard paradigm of structural complexity, that is, to elicit structural properties of complexity classes rather than analyze individual concrete problems. ***