Золотой билет. P, NP и границы возможного - Лэнс Фортноу

Боб пожертвовал обедом, чтобы добить судоку из последнего номера газеты.

«У них тут ошибка. Это решить невозможно!» – восклицает он, совершенно выбившись из сил. На крики приходит его коллега Элис; взглянув на судоку, она видит ту самую головоломку, которую утром решила в метро. Боб зря ругается. На рисунке ниже вы видите решение Элис.

Боб вот-вот сдастся, и Элис хочется его поддержать. Она говорит, что решила задачу, но он ей, конечно, не верит. Он ужасно расстроится, когда увидит в завтрашней газете ответ, так что нужно обязательно убедить его подумать еще. Показать свое решение значит испортить Бобу все удовольствие от процесса; но как доказать, что задача решается, не давая при этом никаких подсказок?

Рис. 8.7. Решение судоку с нулевым разглашением

К счастью, в колледже Элис специализировалась на теоретической информатике и поэтому знает о доказательствах с нулевым разглашением. В голове у нее быстро созревает план действий.

Вернувшись к своему столу и зная, что Боб не может видеть ее за перегородкой, Элис берет цифры от 1 до 9 и случайным образом их упорядочивает.

Рис. 8.8. Новый порядок цифр

С помощью полученной таблицы Элис шифрует свое решение, заменяя 1 на 2, 9 на 3, и т. д., и рисует его на большом листе бумаги. Вот что у нее выходит:

Рис. 8.9. Зашифрованное решение

Дальше Элис аккуратно режет сетку с решением на маленькие квадратики по одной цифре в каждом. Всего квадратиков получается 81. Каждый квадратик она прячет в маленький пакетик и кладет в соответствующую ячейку нарисованной на другом листе пустой сетки.

Рис. 8.10. Решение спрятано

Рис. 8.11. Открытая строка

В левом верхнем пакетике лежит цифра 2, справа от него – цифра 3, и так далее.

Осторожно, без резких движений, Элис относит всю эту конструкцию Бобу и объясняет ему, что именно она сделала. Не раскрывая схему кодировки цифр, она предлагает провести тест. Бобу разрешается выбрать один из двадцати восьми вариантов:

• открыть все пакетики в одной из строк;

• открыть все пакетики в одном из столбцов;

• открыть все пакетики в одном из девяти блоков 3 × 3;

• открыть все пакетики, расположенные на тех же позициях, что и заданные цифры исходной головоломки.

Допустим, Боб решил открыть третью строку. Что он там увидит?

Если бы в строке оказалось две одинаковых цифры, это означало бы, что Элис наврала. Но поскольку решение у нее действительно есть, и она четко объяснила Бобу, что сделала с пакетиками, Боб видит все различные цифры от 1 до 9 в случайном порядке. Тест пройден!

Если Боб решит открыть столбец или блок 3 × 3, результат будет точно таким же.

Теперь предположим, что он выберет последний вариант – «открыть все пакетики, расположенные на тех же позициях, что и заданные цифры исходной головоломки». Открыв пакетики, Боб видит такую картину.

Рис. 8.12. Открытые позиции соответствуют заданным цифрам

Рис. 8.13. Новый порядок цифр

Это единственный случай, когда Боб получает от Элис еще и таблицу кодировки, при помощи которой он проверит, соответствуют ли открытые цифры тем, что были указаны в задаче изначально. Например, согласно схеме, цифра 9 должна была превратиться в цифру 3… так и есть!

Если Элис и правда решила задачу и четко следовала правилам, она пройдет любую проверку. А что же Боб? Получит ли он хоть какую-нибудь подсказку, когда откроет строку, столбец или блок 3 × 3? Исключено: перед ним будут лишь цифры от 1 до 9, расположенные в случайном порядке.

Последний вариант даст ему перестановку цифр, при помощи которой было зашифровано решение. Но что он при этом узнает? Ничего.

Другое дело, если Элис наврала: один из тестов обязательно провалится, и она ничего не сможет с этим поделать. Когда Боб выбирает тест наугад, вероятность попасться на вранье составляет одну двадцать восьмую, или примерно 3,57 %. Не так уж и рискованно, правда? Однако если Элис и Боб проведут 83 эксперимента подряд и при этом будут каждый раз менять схему кодировки, вероятность провалить один из тестов возрастет до 95 %.

Боб убедился, что Элис действительно решила судоку, а ей при этом удалось соблюсти принцип «нулевого разглашения»: о решении Боб знает только то, что оно существует. Эта мысль будет греть его, когда он вернется к головоломке, но справляться ему придется исключительно своими силами.

Мы исходили из предположения, что Боб не хочет слышать никаких подсказок. На случай, если он решит сжульничать и открыть сразу все пакетики, Элис может спрятать цифры в запирающиеся коробочки и по мере необходимости выдавать Бобу ключи.

Теперь представим, что Боб и Элис не работают вместе и вообще находятся в разных городах. Они могут связаться по телефону или электронной почте, однако вместо пакетиков придется придумать что-то другое. Здесь на помощь им придет несложный шифр. Каждому пакетику Элис может присвоить уникальный номер – большое случайное число, последняя цифра которого совпадает с цифрой внутри. Для цифры 2 подойдет, к примеру, 3682502. Затем она зашифрует номера пакетиков своим открытым ключом и отошлет их Бобу. Когда Боб определится с вариантом теста, Элис сообщит ему исходные номера тех пакетиков, которые разрешается открыть. Для проверки Боб повторно зашифрует их открытым ключом и получит те же номера, что Элис выслала ему в начале.