Structural Complexity Theory

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

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.