Bounded Queries and Approximation

本项目通过研究有界查询层次结构中复杂度类的结构，研究了寻找np优化问题近似解的计算复杂性。关于这些复杂性类的许多问题仍然没有解决。例如，不知道多项式时间图灵机对np完全集使用线性数量的oracle查询是否比只使用log n查询的图灵机能够识别更多的语言。最近的工作已经建立了np逼近问题和有界查询层次之间的密切联系。因此，在寻找最佳旅行推销员行程是否可以简化为寻找2-近似行程（最多是最佳行程长度的两倍）的开放问题之间存在直接对应关系。如果这样的减少是可能的，这将意味着对于许多np完全问题，寻找近似解和最优解的复杂性没有显著差异。这将彻底改变目前对np完备性本质的理解。推动这项研究的猜想是，这种减少并不存在。然而，目前，它的存在并没有违反任何常见的棘手假设（例如，P - NP或多项式层次结构不会崩溃）。这个项目的目标是解决关于有界查询层次结构的许多悬而未决的问题。

This project studies the computational complexity of finding approximate solutions to NP-optimization problems through an investigation of the structure of complexity classes in the bounded query hierarchy. Many questions about these complexity classes remain open. For example, it is not known whether a polynomial time Turing machine using a linear number of oracle queries to an NP-complete set can recognize more languages than one which uses only log n queries. Recent works have established close connections between NP-approximation problems and the bounded query hierarchy. As a result, there is a direct correspondence between open questions of whether finding an optimum Traveling Salesman tour can be reduced to finding a 2- approximate tour (one that has at most twice the length of the optimum tour). If such a reduction were possible, it would imply that there is no significant difference in the complexity of finding approximate versus optimum solutions for many NP-complete problems. This would drastically alter the present understanding of the nature of NP-completeness. The conjecture motivating this research is that such a reduction does not exist. However, currently, its existence is not known to violate any of the common intractability assumptions (e.g. that P NP or that the Polynomial Hierarchy does not collapse). The goal of this project is to solve many of the outstanding open questions about the bounded query hierarchy.