Interactive proofs and approximation: reductions from two provers in one round
Interactive proofs and approximation: reductions from two provers in one round
复制标题
交互式证明和近似：一轮中两个证明者的减少
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
M. Bellare
中科院分区：
文献类型：
--
作者：
M. Bellare
作者提出了难以近似的问题在以下领域：系统的代表，网络流，最长路径的图形。在每种情况下，他都表明存在一些delta >0，使得多项式时间近似在最佳值的2/sup log delta n/的因子内意味着NP具有准多项式时间确定性模拟。这些结果是由两个证明器，一轮证明系统的约简导出的，并证明了这种约简对于许多不同类型的问题产生近似结果的困难性的能力。<<ETX>>
The author presents hard to approximate problems in the following areas: systems of representatives, network flow, and longest paths in graphs. In each case he shows that there exists some delta >0 such that polynomial time approximation to within a factor of 2/sup log delta n/ of the optimal implies that NP has quasi polynomial time deterministic simulations. The results are derived by reduction from two prover, one round proof systems, and exemplify the ability of such reductions to yield hardness of approximations results for many different kinds of problems.<<ETX>>