Topics in Computational Complexity

将调查各种计算问题的内在复杂性，希望能够更深入地理解为什么某些问题的解决似乎需要大量的计算资源。作为这一努力的补充，还将研究一些现有算法的预期性能。这项研究所需的主要数学工具可能是组合和概率技术。为了界定研究的范围，从布尔电路、决策树、数据结构、几何计算和算法的数学分析等方面给出了具有代表性的问题。

The inherent complexity of various computational problems will be investigated, in the hope that a deeper understanding may be gained as to why certain problems seem to require a nontrivial amount of computing resources for their solution. Complementary to this effort, the expected performance of a number of existing algorithms will also be studied. The principal mathematical tools needed for this research are likely to be combinatorial and probabilistic techniques. To delineate the scope of this investigation, representative problems are given from Boolean circuits, decision trees, data structures, geometric computations, and the mathematical analysis of algorithms.