Пещера Али-Бабы включает в себя следующий сценарий:
- Пегги выбирает случайный путь (A или B) без какой-либо информации от Виктора.
- Виктор спрашивает (кричит,в пещере) Пегги, чтобы выйти из пещеры с одного из двух концов (А или В), не зная пути входа, выбранного Пегги.
- Пегги выходит по пути, выбранному Виктором.
Для одного доказательства это имеет ту же вероятность, что и случайный случай: если мы назовем P_in
путь, куда вошла Пегги, и V_out
путь, на который Виктор просит Пегги выйти,
- Если
P_in = V_out
, то Пегги может тривиально выйти из пещеры, не зная, как открыть дверь внутрь. - Если
P_in != V_out
, тогда Пегги нужно знать ключ, чтобы перейти с одной стороны пещеры.к другому.
У нас есть следующие равновероятные сценарии:
- P_in = A, V_out = A
- P_in = A, V_out = B
- P_in = B, V_out = A
- P_in = B, V_out = B
ОниЭто равновероятно, потому что Пегги выбирает случайно, а Виктор выбирает случайно, не зная, что выбрала Пегги (это часть с нулевым знанием).
Из предыдущего предположения мы легко получаем, что P(P_in = V_out) = 1/2
: то есть вероятностьспособность Пегги тривиально выйти из пещеры без дополнительных знаний аналогична случайному шансу.
Однако, если Виктор неоднократно просит Пегги войти в пещеру, вероятности увеличиваются.То есть P_in#1 = V_out#1 = 50%
;но P_in#2 = V_out#2 = 50%
(само по себе), что означает из-за условной вероятности (при условии, что события независимы), что для того, чтобы оба раза выйти из пещеры случайным образом:
P(P_in#1 = V_out#1 /\ P_in#2 = V_out#2) = 1/2 * 1/2 = 1/4
ВероятностьПегги, зная, что ключ теперь повышен до 3/4:
P( (P_in#1 != V_out#1 /\ P_in#2 == V_out#2)
|| (P_in#1 == V_out#1 /\ P_in#2 != V_out#2)
|| (P_in#1 != V_out#1 /\ P_in#2 != V_out#2)) =
P( ((P_in#1 != V_out#1 || P_in#1 == V_out#1) /\ P_in#2 == V_out#2)
|| P_in#1 != V_out#1 /\ P_in#2 != V_out#2) =
P( P_in#2 == V_out#2
|| (P_in#1 != V_out#1 /\ P_in#2 != V_out#2)) = 1/2 + (1/2 * 1/2) = 3/4
Причина экспоненциальной сложности заключается в том, что одиночный отказ вызывает недоверие, в то же время накапливая "серию побед"Случайный случай экспоненциально сложен.Таким образом, с учетом предыдущих вероятностей вы получаете O(2 ^ n)
, так как вы получаете «раз два» сложность при каждой попытке.