4431
правка
Сложность биматричного равновесия Нэша: различия между версиями
Перейти к навигации
Перейти к поиску
м
Сложность биматричного равновесия Нэша (посмотреть исходный код)
Версия от 16:21, 29 августа 2021
, 29 августа 2021→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 24: | Строка 24: | ||
Бинарное отношение <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|. NP-полная задача поиска <math>Q_R</math>, задаваемая R, определяется следующим образом: | ||
пусть дано x | пусть дано <math>x \in \{0, 1 \}^*</math>. Если существует y, такое, что <math>(x, y) \in R</math>, то алгоритм возвращает y, в противном случае он возвращает специальную строку «нет». | ||
Отношение R является полным, если для каждого x | Отношение 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>. | ||