We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output $i$ such that $x_i\neq y_i$ (zero-communication setting). We give upper and lower bounds for private coin, public coin, shared entanglement and non-signaling strategies, and give some separations. We show that complexity in the public coin model is upper bounded by Randomized query and Certificate complexity. On the other hand, it is lower bounded by fractional and randomized certificate complexity, making it a good candidate to prove strong lower bounds on randomized query complexity. Complexity in the private coin model is bounded from below by zero-error randomized query complexity. The quantum measure highlights an interesting and surprising difference between classical and quantum query models. Whereas the public coin certificate game complexity is bounded from above by randomized query complexity, the quantum certificate game complexity can be quadratically larger than quantum query complexity. We use non-signaling, a notion from quantum information, to give a lower bound of $n$ on the quantum certificate game complexity of the $OR$ function, whose quantum query complexity is $\Theta(\sqrt{n})$, then go on to show that this ``non-signaling bottleneck'' applies to all functions with high sensitivity, block sensitivity or fractional block sensitivity. We consider the single-bit version of certificate games (inputs of the two players have Hamming distance $1$). We prove that the single-bit version of certificate game complexity with shared randomness is equal to sensitivity up to constant factors, giving a new characterization of sensitivity. The single-bit version with private randomness is equal to $\lambda^2$, where $\lambda$ is the spectral sensitivity.
翻译:我们引入并研究证书游戏的复杂性,这是一个基于赢得游戏概率的复杂度的衡量标准,它让两个玩家获得具有不同功能值的投入,并且被要求输出美元,例如$x_i\neq y_i$(零通信设置)。我们给私人硬币、公共硬币、共同纠缠和非信号策略提供上下界限。我们显示,公共硬币模式的复杂性由随机查询和证书复杂度的上限约束。另一方面,它受分数和随机化的证书复杂度约束,使得它成为在随机化查询复杂度上证明强度较低界限的良好候选人。私人硬币模型的复杂度从下界限到零或随机随机随机的查询复杂度。量量测量模型的复杂度由随机化的复杂度决定,量证书游戏的复杂度可以比量的复杂度大得多。我们使用非指派的,一个来自量级的敏感度信息概念,在随机性查询复杂度中的最小度值为$美元,然后用硬度的硬度显示, 硬度证书的复杂度函数是美元。