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

Бинарное отношение <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>-[[Классы P и NP|полная]] задача поиска <math>Q_R</math>, задаваемая R, определяется следующим образом:

пусть дано <math>x \in \{0, 1 \}^*</math>. Если существует y, такое, что <math>(x, y) \in R</math>, то алгоритм возвращает y, в противном случае он возвращает специальную строку «нет».