精选理由
这篇论文告诉你，就算是最简单的二次多项式，求极小极大问题的近似解也是超级难的，还顺带证明了博弈论里某些游戏也是难到头。
论文证明了在超立方体上计算二次多项式的近似稳定点是PPAD难的。即使在多项式为多重线性且每个变量出现在至多3个单项式的情况下，该结论依然成立。近似因子可达到逆多项式精度。作为直接推论，首次得到了两队零和多项矩阵博弈的PPAD困难性结果。
AI 翻译 · 中文
论文证明了在超立方体上计算二次多项式的近似稳定点是PPAD难的。即使在多项式为多重线性且每个变量出现在至多3个单项式的情况下，该结论依然成立。近似因子可达到逆多项式精度。作为直接推论，首次得到了两队零和多项矩阵博弈的PPAD困难性结果。
We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials. This holds even when the polynomials are multilinear, each variable appears in at m…