Первым делом застелем пол на нашем складе чистой бумагой, чтобы у нас было место для предоставления нашей сотовой сети. После этого выходим со склада. Теперь на склад могут войти представитель большой корпорации, с которой у нас возникли разногласия. Он может смешать все карандаши и выбрать три, которые ему понравятся. Например, красного, голубого и фиолетового цвета, а также цвет для обозначения решения. Цвет роли не играет. Перед своим уходом представитель корпорации накрыл все вершины шляпами. После того, как мы войдём в склад, мы увидим:
Корпорация тщательно скрыла свои секреты, но нас не устраивает такой подход. Мы ведь не знаем, что под шляпами, возможно цвета там просто разбросаны хаотически или их вообще там нет.
Но корпорация разрешает нам открыть одну грань представленного графа(одну линию между шляпами), открыв часть решения.
Стоит отметить, что есть два варианта исхода. Если вершины имеют один цвет или не окрашены, значит нас обманули. А если вершины разных цветов, то решение имеется.
С первым вариантом всё ясно. А вот второй требует пояснений. Даже при разных цветах под шляпами у корпорации есть возможность для обмана, решение может быть не верным.
Для исключения этого, необходимо просто запустить протокол снова. На наших чистых листах корпорация другими случайными цветами снова предоставляет решение графа и накрывает их шляпами. Мы произвольно выбираем новые вершины. Если и сейчас всё в порядке, то корпорации должно было повезти два раза подряд, а это намного сложнее. Теоретически это возможно, но вероятность этого события значительно ниже. Просчитать эту вероятность можно формуле (E-1)/E*(E-1)/E. Для примера с тысячей граней это 99,8%.
Но мы не ограничены в попытках и можем проверять корпорацию сколько угодно, пока не посчитаем, что доверяем ей. Теоретически, даже с большим количеством проверок всегда остаётся шанс на обман, но мы остановимся на ничтожной вероятности, которая допустима в практических задачах. И тогда мы сможем завершить сделку и отдать деньги корпорации.
Корпорация при таком подходе тоже защищена. Даже если мы попытаемся как это анализировать и систематизировать наши попытки, то нам ничего не удастся. Ведь при каждой попытке корпорация будет использовать новые случайные цвета. У нас будет лишь ограниченная информация, которую связать в одно целое не получится. Таким образом шляпы помогут обоим участникам сделки.
Корпорация тщательно скрыла свои секреты, но нас не устраивает такой подход. Мы ведь не знаем, что под шляпами, возможно цвета там просто разбросаны хаотически или их вообще там нет.
Но корпорация разрешает нам открыть одну грань представленного графа(одну линию между шляпами), открыв часть решения.
Стоит отметить, что есть два варианта исхода. Если вершины имеют один цвет или не окрашены, значит нас обманули. А если вершины разных цветов, то решение имеется.
С первым вариантом всё ясно. А вот второй требует пояснений. Даже при разных цветах под шляпами у корпорации есть возможность для обмана, решение может быть не верным.
Для исключения этого, необходимо просто запустить протокол снова. На наших чистых листах корпорация другими случайными цветами снова предоставляет решение графа и накрывает их шляпами. Мы произвольно выбираем новые вершины. Если и сейчас всё в порядке, то корпорации должно было повезти два раза подряд, а это намного сложнее. Теоретически это возможно, но вероятность этого события значительно ниже. Просчитать эту вероятность можно формуле (E-1)/E*(E-1)/E. Для примера с тысячей граней это 99,8%.
Но мы не ограничены в попытках и можем проверять корпорацию сколько угодно, пока не посчитаем, что доверяем ей. Теоретически, даже с большим количеством проверок всегда остаётся шанс на обман, но мы остановимся на ничтожной вероятности, которая допустима в практических задачах. И тогда мы сможем завершить сделку и отдать деньги корпорации.
Корпорация при таком подходе тоже защищена. Даже если мы попытаемся как это анализировать и систематизировать наши попытки, то нам ничего не удастся. Ведь при каждой попытке корпорация будет использовать новые случайные цвета. У нас будет лишь ограниченная информация, которую связать в одно целое не получится. Таким образом шляпы помогут обоим участникам сделки.
