论文标题
NP Oracle认证
Certification with an NP Oracle
论文作者
论文摘要
在认证问题中，算法给出了带有证书复杂性$ k $和一个输入$ x^\ star $的函数$ f $，目标是找到尺寸$ \ le \ le \ text {poly}（k）$的证书，$ f $ in $ x^\ star $。这个问题在$ \ Mathsf {np}^{\ Mathsf {np}} $中，并假设$ \ Mathsf {p} \ ne \ ne \ Mathsf {np} $，不在$ \ Mathsf {p} $中。因此，可以追溯到1984年Valiant的先前工作试图通过对$ F $（例如单调性）施加假设来设计有效的算法。 我们的第一个结果是$ \ Mathsf {Bpp}^{\ Mathsf {np}} $算法的一般问题。关键要素是变量平衡影响的新概念，这是一种自然影响变体，可以纠正函数的偏见。可以通过统一生成来准确估算平衡的影响，而经典的$ \ Mathsf {Bpp}^{\ Mathsf {np}} $算法以后一种任务而闻名。 然后，我们考虑具有更严格的实例保证的认证：对于每个$ x^\ star $，找到一个证书，其尺寸尺寸为$ x^\ star $的最小证书的规模。与我们的第一个结果形成鲜明对比的是，我们表明此问题是$ \ Mathsf {np}^{\ Mathsf {np}} $ - 甚至很难近似。我们获得了最佳的不Xibibibibility比率，在较高级别的多项式层次结构中增加了少数问题，以确保最佳的不易Xibibibibibility。我们的证明涉及将比特固定分散器用于间隙扩增的新颖使用。
In the certification problem, the algorithm is given a function $f$ with certificate complexity $k$ and an input $x^\star$, and the goal is to find a certificate of size $\le \text{poly}(k)$ for $f$'s value at $x^\star$. This problem is in $\mathsf{NP}^{\mathsf{NP}}$, and assuming $\mathsf{P} \ne \mathsf{NP}$, is not in $\mathsf{P}$. Prior works, dating back to Valiant in 1984, have therefore sought to design efficient algorithms by imposing assumptions on $f$ such as monotonicity. Our first result is a $\mathsf{BPP}^{\mathsf{NP}}$ algorithm for the general problem. The key ingredient is a new notion of the balanced influence of variables, a natural variant of influence that corrects for the bias of the function. Balanced influences can be accurately estimated via uniform generation, and classic $\mathsf{BPP}^{\mathsf{NP}}$ algorithms are known for the latter task. We then consider certification with stricter instance-wise guarantees: for each $x^\star$, find a certificate whose size scales with that of the smallest certificate for $x^\star$. In sharp contrast with our first result, we show that this problem is $\mathsf{NP}^{\mathsf{NP}}$-hard even to approximate. We obtain an optimal inapproximability ratio, adding to a small handful of problems in the higher levels of the polynomial hierarchy for which optimal inapproximability is known. Our proof involves the novel use of bit-fixing dispersers for gap amplification.
