Аннотация:
В классической модели коммуникационной сложности, введённой Эндрю Яо в 1979 году, рассматривается игра для двух игроков, Алисы и Боба, которые хотят вычислить f(x,y) для некоторой функции f, причём Алисе известно только значение x, а Бобу - только значение y. Для решения этой задачи Алиса и Боб могут общаться, посылая друг другу битовые сообщения по одному биту за раунд. Важное свойство этой коммуникационной модели заключается в том, что на каждом раунде общения один из игроков посылает некоторое битовое сообщение, а другой игрок обязательно его принимает. Коммуникационная сложность функции определяется как минимальное количество битов, которые нужно передать, чтобы вычислить f(x,y) для всех возможных пар x,y.
Эта модель была обобщена в 2018 году Гувером, Импальяццо, Михайлиным и Смалем до модели, описывающей общение по так называемому полудуплексному каналу. Широко известный пример полудуплексного канала в обычной жизни - это общение при помощи раций: для передачи сообщения по рации нужно зажать кнопку передачи (принцип «push-to-talk»), в то же время на принимающей стороне в этот момент кнопка должна быть отпущена. Если два человека пытаются передавать сообщения одновременно (т.е. у обоих рации находятся в режиме передачи), то они не слышат друг друга. Есть разные модели полудуплексных коммуникационных протоколов: модель с тишиной (если оба пытаются принять сообщения, то они получают специальный символ "тишина"), модель с нулем (они принимают нулевой бит) и модель с противником (они принимают произвольные биты, выбираемые противником). Для большинства функций коммуникационная сложность с тишиной и с нулем меньше классической коммуникационной сложности. Однако до сих пор было неизвестным, различается ли коммуникационная сложность с противником от классической. Мы приведем пример функции, для которой полудуплексная коммуникационная сложность с противником строго меньше классической коммуникационной сложности.
