Визирь-сладкоежка
Задача
а) Давным-давно жили-были Султан и его Визирь. Султан в свободное от работы время увлекался математикой и часто просил Визиря (который все знал) доказать какую-нибудь теорему, которая ему самому была не по силам. Если теорема была верная, то Визирь ее, конечно, доказывал, а Султан слушал и пытался разобраться в доказательстве. Правда, в математике он был не очень силен, так что с вероятностью 1/3 мог заподозрить ошибку в абсолютно верном доказательстве. Иногда Визирь ради шутки давал доказательство неверной теоремы. С той же вероятностью 1/3 Султан мог не заметить ошибки — в зависимости от настроения, которое у султанов не очень-то постоянное. Что делать Султану, чтобы проверить доказательство с вероятностью ошибиться не более 1/10?
б) Устав от шуток Визиря, Султан велел отрубить ему голову, но вовремя спохватился и придумал как решить проблему иначе. Дело в том, что у Визиря была одна слабость: он очень любил халву и делал все возможное, чтобы побольше ее получить (если говорить формально, то Визирь стремился максимизировать математическое ожидание количества полученной халвы). Султан установил правила выдачи халвы так, что смог заставить Визиря честно отвечать, верная теорема или нет. Как ему это удалось?
в) Однажды, лежа в тени пальмы, Султан захотел узнать, сколько простых чисел, меньших 10000, и вызвал для этого Визиря. Султан уверен, что ему достаточно проверить простоту одного случайно выбранного числа (больше ему проверять лень), и в зависимости от результата и ответа Визиря наградить того порцией халвы. Как ему установить правила выдачи халвы, чтобы Визирь дал верный ответ?
Подсказка 1
То, что у Султана непостоянное настроение, означает, что если он попробует несколько раз разобраться в одном и том же доказательстве, то у него могут получиться разные результаты (то есть события, состоящие в том, что Султан ошибся, являются независимыми).
Подсказка 2
Визирь может либо попытаться доказать теорему, либо сразу сказать, что она неверная. Султану надо сделать так, чтобы Визирю было выгодно доказывать в том и только том случае, когда теорема верна.
Подсказка 3
Количество выданной халвы может зависеть только от результата проверки одного числа на простоту и числа, которое по словам Визиря является ответом. Понятно, что вероятность того, что случайно выбранное число будет простым, пропорциональна правильному ответу. Надо подобрать количество халвы (например, в виде многочлена от ответа Визиря) так, чтобы максимум математического ожидания достигался в случае верного ответа.
Решение
а) Пусть Султан пытается разобраться в доказательстве 2n + 1 раз и принимает его тогда и только тогда, когда он счел его верным не менее, чем в n проверках . Тогда ошибиться он может, только если он правильно проверит доказательство не более чем n раз. Вероятность этого равна \(p = \sum\limits_{k=0}^{n} C_{2n+1}^k \left(\frac{2}{3}\right)^k \left(\frac{1}{3}\right)^{\left((2n + 1)-k\right)}\) (кстати говоря, это значение функции биномиального распределения). Можно проверить, что при n = 7 получается p < 0,09, что удовлетворяет нужному ограничению.
б) Рассмотрим следующее правило выдачи халвы: если Визирь сказал, что теорема неверна, Султан награждает его одним куском халвы. Если же Визирь дал доказательство, то Султан выдает два куска халвы, если оно показалось ему верным, а в противном случае вообще не дает халву. В случае, если Визирь отказывается решать задачу, он получает гарантированную порцию в один кусок халвы. Рассмотрим случай, когда он дал доказательство. Если теорема верна, то вероятность того, что Султан поймет доказательство равна 2/3 и, следовательно, математическое ожидание полученной халвы равно \(\frac{2}{3} \cdot 2 + \frac{1}{3} \cdot 0 = \frac{4}{3} > 1\), то есть Визирю невыгодно отказываться. Пусть теперь теорема не является верной, тогда Султан распознает ошибку в подложном доказательстве с вероятностью 2/3 и матожидание выгоды будет равно \(\frac{2}{3} \cdot 0 + \frac{1}{3} \cdot 1 = \frac{2}{3} < 1\), то есть Визирю выгоднее сразу сказать, что теорема неверна. Мы получили, что в любом случае Визирь честно ответит, верна теорема или нет, что и требовалось.
в) Обозначим ответ Визиря за m, а искомое число простых чисел — за n. Заметим, что вероятность случайно попасть в простое число равна \(q = \frac{n}{10000}\). По «версии» Визиря эта вероятность равна \(p = \frac{m}{10000}\). Тогда, если установить количество выданной халвы R следующим образом:
то матожидание количества полученной Визирем халвы будет равно
Чтобы определить, когда достигается максимальное значение найденного матожидания, приравняем к нулю его производную по p:
откуда получаем, что p = q и, следовательно, максимум выгоды Визиря достигается в том случае, когда он отвечает правильно.
Послесловие
Эта задача — мимолетный взгляд на теорию интерактивных доказательств (см. Interactive proof system) и, в частности, на рациональные доказательства, идея которых возникла совсем недавно (P. D. Azar, S. Micali, 2012. Rational Proofs). Метафора со всезнающим Визирем и горе-математиком Султаном формализуется следующим образом: в доказательстве участвуют две стороны: доказывающая (prover) и проверяющая (verificator). Причем, если вычислительные возможности прувера обычно никак не ограничены, то верификатор может тратить на вычисление время, ограниченное многочленом от длины входных данных (в теории сложности вычислений класс задач, которые могут быть решены при таких ограничениях на время, обозначается P). В модели рациональных доказательств дополнительно вводится функция вознаграждения прувера — халва в нашей метафоре. Решение задачи дает понять, что верификатор может в таких условиях получать ответ на вычислительно сложные задачи общаясь даже с ненадежным прувером.
Не вдаваясь более в тонкости формализма, посмотрим, как подобные алгоритмы могут применяться на практике, например, в интернете. Алгоритм верификатора работает за время, ограниченное многочленом, — проще говоря, быстро. Это позволяет, например, запустить сеть распределенных вычислений, к которой любой желающий может подключить свой компьютер (выступающий прувером), а центральный сервер сможет быстро проверять все поступающие решения (ведь пользователи могут запускать не исходную программу, а модификацию, пытающуюся обмануть сервер, чтобы, например, дестабилизировать его работу).
Чуть менее очевидное приложение — метод защиты от DoS-атак (при которых сервер заваливают бесполезными запросами, так что у него не остается времени на настоящую работу), называемый proof-of-work. Идея состоит в следующем: пусть чтобы получить разрешение на запрос к серверу, клиент должен сначала решить сложную задачу. Тогда на каждый запрос он будет тратить много своего времени, и это снижает эффективность атаки. Серверу же легко проверять, что ответ правильный, и он не тратит много ресурсов, даже если его заваливают неправильными запросами.
