Cтраница 4
Задачу о клике могут представлять и другие языки. Например, можно было бы потребовать, чтобы постоянная k стояла за, а не перед графом. Но для любых двух таких языков должен существовать такой полином р, что цепочку w, представляющую частный случай задачи о клике в одном языке, можно за время р ( М) преобразовать в цепочку, представляющую тот же частный случай этой задачи в другом языке. Таким образом, когда речь идет о принадлежности классу 9 или ЖУ, точный выбор языка для представления задачи о клике неважен, если применяется стандартное кодирование. [46]
В большинстве игр этого типа возможны следующие исходы: выигрыш, проигрыш и ничья. Игры, в которых возможна ничья, можно упрощенно считать играми с двумя исходами - выигрыш и не-выигрыш. Игрок может выиграть в некоторой нетерминальной позиции с ходом игрока ( позиции игрока), если в ней существует какой-нибудь разрешенный ход, приводящий к выигрышу. Эти правила находятся в полном соответствии с представлением задач в форме И / ИЛИ-дерева, которое мы обсуждали в гл. [47]