Полудуплексная коммуникационная сложность с противником может быть меньше классической коммуникационной сложности

Н. К. Верещагин^ab, М. В. Дектярев<sup>a

a</sup> Механико-математический факультет, Московский государственный университет имени М. В. Ломоносова
^b Факультет компьютерных наук,Национальный исследовательский университет «Высшая школа экономики», г. Москва

Аннотация: Полудуплексная коммуникационная сложность с противником определена в работе [2]. Полудуплексные коммуникационные протоколы обобщают классические протоколы, определенные Эндрю Яо в [11]. До сих пор было неизвестным, различаются ли коммуникационные сложности, определяемые этими моделями. В настоящей работе дается ответ на этот вопрос: приведен пример функции, для которой полудуплексная коммуникационная сложность с противником строго меньше классической коммуникационной сложности.
Библиография: 11 названий.

Ключевые слова: коммуникационная сложность, трудные множества, полудуплексная коммуникационная сложность.

MSC: 68Q11, 68R10

Поступила в редакцию: 13.07.2024 и 17.12.2024

DOI: 10.4213/sm10159

 Англоязычная версия: Sbornik: Mathematics, 2025, 216:6, 742–779

Реферативные базы данных:

• 
• 
• 
•