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

Этот экземпляр определяет ориентированный граф G = (V, E) с V = f0; 1gn. Дуга (U; V) 2 E в том и только том случае, если vis – вторая компонента M(U), а u – первая компонента M(v).

Результатом решения задачи LEAFD является ориентированный лист G, отличный от 0n. Здесь вершина называется ориентированным листом, если сумма ее полустепени исхода и полустепени захода равна единице.

Задача поиска в PPAD называется полной в PPAD (или PPAD-полной), если существует редукция от LEAFD до нее за полиномиальное время.

Теорема [2]. Задачи 2-Nash и Nash являются PPAD-полными.