4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 6: | Строка 6: | ||
Захватывающий прорыв, достигнутый Даскалакисом, Голдбергом и Пападимитриу [4] для игр с четырьмя или более игроками, свидетельствует о том, что вычисление равновесия Нэша, вероятно, является трудным. Было доказано, что задача является | Захватывающий прорыв, достигнутый Даскалакисом, Голдбергом и Пападимитриу [4] для игр с четырьмя или более игроками, свидетельствует о том, что вычисление равновесия Нэша, вероятно, является трудным. Было доказано, что задача является <math>\mathcal PPAD</math>-полной (аргументы полиномиальной четности на ориентированных графах – polynomial parity argument, directed version) – этот класс сложности был введен Пападимитриу в работе [9]. Результаты в [4] основываются на технике, разработанной в [6]. Затем эта оценка сложности была улучшена для случая трех игроков Ченом и Денгом [1], а также Даскалакисом и Пападимитриу [5] – независимо друг от друга и с использованием разных доказательств. Наконец, Чен и Денг [2] доказали, что NASH – задача нахождения равновесия Нэша в биматричной игре (или игре для двух игроков) – является <math>\mathcal PPAD</math>-полной. | ||
Строка 22: | Строка 22: | ||
== Основные результаты == | == Основные результаты == | ||
Бинарное отношение <math>R \subset \{ 0, 1 \}^* \times \{0, 1 \}^*</math> является ''полиномиально сбалансированным'', если существует полином ''p'', такой, что для всех пар <math>(x, y) \in R</math> верно <math>|y| \le p(|x|)</math>. Это отношение ''вычислимо за полиномиальное время'', если для каждой пары (x,y) можно решить, верно ли <math>(x, y) \in R</math>, за время, полиномиальное относительно |x| + |y|. NP-полная задача поиска <math>Q_R</math>, задаваемая R, определяется следующим образом: | Бинарное отношение <math>R \subset \{ 0, 1 \}^* \times \{0, 1 \}^*</math> является ''полиномиально сбалансированным'', если существует полином ''p'', такой, что для всех пар <math>(x, y) \in R</math> верно <math>|y| \le p(|x|)</math>. Это отношение ''вычислимо за полиномиальное время'', если для каждой пары (x,y) можно решить, верно ли <math>(x, y) \in R</math>, за время, полиномиальное относительно |x| + |y|. <math>\mathcal NP</math>-полная задача поиска <math>Q_R</math>, задаваемая R, определяется следующим образом: | ||
пусть дано <math>x \in \{0, 1 \}^*</math>. Если существует y, такое, что <math>(x, y) \in R</math>, то алгоритм возвращает y, в противном случае он возвращает специальную строку «нет». | пусть дано <math>x \in \{0, 1 \}^*</math>. Если существует y, такое, что <math>(x, y) \in R</math>, то алгоритм возвращает y, в противном случае он возвращает специальную строку «нет». | ||
Отношение R является ''полным'', если для каждого <math>x \in \{0, 1 \}^*</math> существует y, такое, что <math>(x, y) \in R</math>. Следуя [7], обозначим за TFNP класс всех NP-полных задач поиска, заданных полными отношениями. Задача поиска <math>Q_{R_1} \in TFNP</math> ''полиномиально сводима'' к задаче <math>Q_{R_2} \in TFNP</math>, если существует пара полиномиально вычислимых функций (f, g), таких, что для каждого x из <math>R_1</math> в случае, если y удовлетворяет условию <math>(f(x), y) \in R_2</math>, верно <math>(x, g(y)) \in R_1</math>. Более того, <math>Q_{R_1}</math> и <math>Q_{R_2}</math> полиномиально эквивалентны, если <math>Q_{R_2}</math> также сводима к <math>Q_{R_1}</math>. | Отношение R является ''полным'', если для каждого <math>x \in \{0, 1 \}^*</math> существует y, такое, что <math>(x, y) \in R</math>. Следуя [7], обозначим за <math>\mathcal TFNP</math> класс всех <math>\mathcal NP</math>-полных задач поиска, заданных полными отношениями. Задача поиска <math>Q_{R_1} \in \mathcal{TFNP}</math> ''полиномиально сводима'' к задаче <math>Q_{R_2} \in \mathcal{TFNP}</math>, если существует пара полиномиально вычислимых функций (f, g), таких, что для каждого x из <math>R_1</math> в случае, если y удовлетворяет условию <math>(f(x), y) \in R_2</math>, верно <math>(x, g(y)) \in R_1</math>. Более того, <math>Q_{R_1}</math> и <math>Q_{R_2}</math> полиномиально эквивалентны, если <math>Q_{R_2}</math> также сводима к <math>Q_{R_1}</math>. | ||
Класс сложности PPAD является подклассом TFNP, содержащим все задачи поиска, которые полиномиально сводимы к: | Класс сложности <math>\mathcal PPAD</math> является подклассом <math>\mathcal TFNP</math>, содержащим все задачи поиска, которые полиномиально сводимы к: | ||
Строка 46: | Строка 46: | ||
Задача поиска в PPAD называется ''полной'' в PPAD (или PPAD-полной), если существует редукция от LEAFD до нее за полиномиальное время. | Задача поиска в <math>\mathcal PPAD</math> называется ''полной'' в <math>\mathcal PPAD</math> (или <math>\mathcal PPAD</math>-полной), если существует редукция от LEAFD до нее за полиномиальное время. | ||
'''Теорема [2]. Задачи 2-NASH и NASH являются PPAD-полными.''' | '''Теорема [2]. Задачи 2-NASH и NASH являются <math>\mathcal PPAD</math>-полными.''' | ||
== Применение == | == Применение == | ||
Строка 58: | Строка 58: | ||
Хотя многие считают, что PPAD является трудным | Хотя многие считают, что <math>\mathcal PPAD</math> является трудным в <math>\mathcal P</math>, однако веских доказательств или интуитивных соображений в пользу этого мнения нет. Остается открытым естественный вопрос: можно ли строго доказать, что класс <math>\mathcal PPAD</math> является трудным, при одном из общепринятых в теоретической информатике предположений, таких как «<math>\mathcal NP</math> не находится в <math>\mathcal P</math>» или «существует вычислительно необратимая функция»? Такой результат был бы чрезвычайно важным как для теории вычислительной сложности, так и для теории алгоритмических игр. | ||
== См. также == | == См. также == |
правка