Lower Bounds for Time-space Tradeoffs, Data Structures, and Proof Complexity

本研究解决了计算复杂性的三个领域的几个问题。每种情况下的总体目标都是了解计算机能力的限制以及在其上运行的算法。第一个研究领域涉及计算的处理时间和存储需求之间的权衡：什么时候可以使用既快速又使用少量存储的算法来解决问题，什么时候可以限制在这两种资源之间进行权衡，只以额外的运行时间为代价来减少存储需求？第二个研究领域涉及数据结构效率的提高，这可能是通过利用现代处理器中的广泛指令来实现的，这些处理器可以一次对整个计算机单词进行操作。第三个研究领域涉及解决NP-hard搜索问题的算法分析。当许多这样的算法搜索但没有找到问题的解决方案时，它们隐含地提供了不存在这样的解决方案的证明。在这一部分的研究中，研究人员分析了这些隐式证明的形式，以显示这些搜索算法效率的局限性。更具体地说，时空权衡的研究建立在研究者之前关于时空权衡下界的工作基础上，旨在将这些结果扩展到其他自然问题，如图连通性和改进当前下界技术所显示的复杂性限制。数据结构的研究是在随机存取机的模型中进行的，随机存取机对字大小的数量进行任意单位成本的操作。这个数据结构研究的目标是了解这个模型中可能的算法改进的局限性，特别是对于最近邻查询、优先级队列、排序和垃圾收集。对np搜索算法复杂度的研究主要集中在随机结构的协np性质的证明复杂度上。我们的目标是表明，对于随机选择的输入，自然证明系统（如resolution）几乎总是需要指数级的隶属性证明，以对应于自然NP问题的对偶。这样做的一个结果是证明了解决NP问题的大型算法在大量输入上需要指数级的时间。

This research addresses several problems in three areas of computational complexity. The overall objective in each case is to understand the limits of the capabilities of computers and the algorithms that run on them. The first area of research concerns tradeoffs between the processing time and storage requirements of computations: When can one solve problems using algorithms that are both fast and use small amounts of storage and when is one limited to trading off thesetwo resources, reducing storage requirements only at the cost of additional running time?The second area of research concerns the increased efficiencies in data structures that are possible by taking advantage of the wide range of instructions in modern processors that operate on entire computer words at once.The third area of research involves the analysis of algorithms to solve NP-hard search problems.When many such algorithms search but do not find a solution to a problem,they implicitly provide proofs that no such solution exists.In this portion of the research, the investigators analyze the form of these implicit proofs to show the limits of the efficiencies of these search algorithms.More specifically, the research in time-space tradeoffs builds on the investigators' previous work on time-space tradeoff lower bounds and is aimed at extending these results to other natural problems such as graph connectivity and improving the complexity limits shown by current lower bound techniques.The research in data structures works in the model of random-access machines with arbitrary unit-cost operations on word-size quantities.The goal of this data structure research is to understand the limits of thealgorithmic improvements possible in this model, particularly for nearest-neighbor queries, priority queues, sorting, and garbage collection.The research on the complexity of NP-search algorithms focuses onthe proof complexity of co-NP properties of random structures.The goal is to show that for randomly-chosen inputs, natural proof systems such as resolution almost always require exponential-size proofs of membership in the co-NP sets corresponding to the duals of natural NP problems.A consequence of this would be proofs that large classes of algorithms for solving the NP problems require exponential time on large numbers of inputs.