Bounded Queries and Approximation

该项目通过研究有界查询层次结构中复杂类的结构来研究寻找NP-优化问题的近似解的计算复杂性。关于这些复杂性类别的许多问题仍然悬而未决。例如，对于NP-完全集，使用线性数量的Oracle查询的多项式时间图灵机是否可以识别比仅使用logn查询的语言更多的语言，这是未知的。最近的工作在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.