Structural Complexity Theory

可行计算的结构决定了一个人能否有效地解决自然和现代世界提出的优化问题。这项研究的长期目标是通过了解为什么某些问题可能缺乏计算上可行的算法来了解哪些问题有有效的解决方案。特别感兴趣的是复杂性类之间的结构关系，以及复杂性类的内部结构。虽然该项目打算广泛地研究这一领域，但重点将通过两个主题来进行：(A)处理不可预测的执行顺序；(B)稀疏集的性质。关于第一个主题，这个项目调查了可以通过大量短子任务计算的语言类，每个子任务都给出了在它之前执行的子任务的(小)结果。对于子任务的调度是琐碎和固定的情况，蔡和Furst等人已经研究过这一点。然而，该项目研究了子任务的执行顺序不可预测的情况。在第二个主题上，研究了与稀疏集有关的几个问题(稀疏集是“低信息含量集”的一个经典例子)。

The structure of feasible computations determines whether one can efficiently solve the optimization problems posed by nature and the modern world. The long-term goal of this research is to understand which problems have efficient solutions, via learning why certain problems may lack computationally feasible algorithms. Of particular interest are the structural relationships between complexity classes, and the internal structure of complexity classes. Though the project intends to broadly investigate this area, focus will be given to the research via two themes: (a) dealing with unpredictable execution order; and (b) the properties of sparse sets. On the first topic, this project investigates the class of languages computable via a large number of short subtasks, each of which is given the (small) result of the subtask that executed before it. This has been studied by Cai and Furst and others for the case where the scheduling of the subtasks is trivial and fixed. However, the project studies the case in which the order in which the subtasks execute is unpredictable. On the second topic, several issues dealing with sparse sets (which are a classic examples of `sets of low information content`) are examined.