PPAD-сложность для мин-макс оптимизации квадратичных полиномов
Вычисление приближенных стационарных точек мин-макс оптимизации на гиперкубе для квадратичных полиномов является PPAD-сложным. Этот результат верен даже для мультилинейных полиномов, где каждая переменная появляется в максимум в трех мономах, с обратными полиномиальными факторами приближения. В результате, две команды нулевых сумм полиматричных игр доказаны как PPAD-сложные.