Александр Александрович Разборов

Коммуникационная сложность.

А.А.Разборов планирует провести два занятия.

На марсоходе и Земле находятся два файла, которые требуется сравнить на предмет наличия расхождений. Можно ли это сделать способом менее дорогостоящим, нежели просто полностью переслав один из них?

Тот же вопрос с той разницей, что марсоходу разрешается подбрасывать монетку, а правильный ответ должен получиться с вероятностью 99.99999%?

На этот раз на Марсе и Земле составили по списку (например, возможных поломок оборудования или областей, где может находиться вода). Есть ли способ узнать о наличии в обоих списках общего элемента более экономный, чем просто переслать один из списков целиком?

И поможет ли на этот раз монетка...

Или, может быть, квантовый компьютер?

Если Вы не в состоянии сходу ответить на эти вопросы и (!!) обосновать свои ответы, приходите на занятия по коммуникационной сложности. Предварительных знаний не требуется, хотя для понимания места коммуникационной сложности в общей картине мироздания (а оно, безусловно, не сводится к развлекательным примерам) было бы полезно посещение двух первых лекций курса Ю.Л.Притыкина.

Organization Committee e-mail:
dubna@mccme.ru