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

Бинарное отношение R С f0; 1g x {0,1}* является полиномиально сбалансированным, если существует полином p такой, что для всех пар (x;y) 2 R верно jyj < p(jxj). Это отношение вычислимо за полиномиальное время, если для каждой пары (x,y) можно решить, верно ли (x; y) 2 R, за время, полиномиальное относительно jxj + jyj. NP-полная задача поиска QR, заданная R, определяется следующим образом: пустьдано x 2 f0;1}*. Если существует y, такое, что (x; y) 2 R, то алгоритм возвращает y, в противном случае он возвращает специальную строку «нет».