Сложность биматричного равновесия Нэша: различия между версиями

Упомянутая последовательность работ показывает, что игры с (r + 1) игроками полиномиально сводимы к играм с r игроками для любого <math>r \ge 2</math>, но редукция осуществляется путем сведения игр с (r + 1) игроками сначала к задаче с фиксированной точкой, а затем к играм с r игроками. Существует ли естественная редукция, которая переходит непосредственно от игр с (r + 1)игроками к играм с r игроками? Подобная редукция могла бы обеспечить лучшее понимание поведения в многопользовательских играх.

Хотя многие считают, что <math>\mathcal PPAD</math> является трудным в <math>\mathcal P</math>, однако веских доказательств или интуитивных соображений в пользу этого мнения нет. Остается открытым естественный вопрос: можно ли строго доказать, что класс <math>\mathcal PPAD</math> является трудным, при одном из общепринятых в теоретической информатике предположений, таких как «<math>\mathcal NP</math> не находится в <math>\mathcal P</math>» или «существует вычислительно необратимая функция»? Такой результат был бы чрезвычайно важным как для теории вычислительной сложности, так и для теории алгоритмических игр.