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

На марсоходе и Земле находятся два файла, которые требуется сравнить на предмет наличия расхождений. Можно ли это сделать способом менее дорогостоящим, нежели просто полностью переслав один из них?
Тот же вопрос с той разницей, что марсоходу разрешается подбрасывать монетку, а правильный ответ должен получиться с вероятностью 99.99999%?
На этот раз на Марсе и Земле составили по списку (например, возможных поломок оборудования или областей, где может находиться вода). Есть ли способ узнать о наличии в обоих списках общего элемента более экономный, чем просто переслать один из списков целиком?
И поможет ли на этот раз монетка...
Или, может быть, квантовый компьютер?
Если Вы не в состоянии сходу ответить на эти вопросы и (!!) обосновать свои ответы, приходите на занятия по коммуникационной сложности. Предварительных знаний не требуется, хотя для понимания места коммуникационной сложности в общей картине мироздания (а оно, безусловно, не сводится к развлекательным примерам) было бы полезно посещение двух первых лекций курса Ю.Л. Притыкина.