Искусство мыслить рационально. Шорткаты в математике и в жизни

Но теперь все совсем иначе. В каждом матче могут быть присуждены либо три очка – их получает победитель, – либо два, которые делят между собой команды, сыгравшие вничью. Если все матчи сезона будут сыграны вничью, сумма очков по-прежнему будет равна 760. Но, если не будет ни одной ничьей, сумма составит 3 × 20 × 19 = 1140 очков. Появление этих вариаций суммарного количества очков привело к тому, что действовавший до этого алгоритм, который позволял мне понять, остаются ли у моей команды математические шансы на победу в лиге, перестал работать.

Все эти задачи замечательны тем, что, если удается найти какое-нибудь решение, можно быстро проверить, действительно ли оно подходит к задаче. Я называю их «задачами об иголке в стоге сена»: сначала нужно проделать долгую, изнурительную работу, чтобы понять, где именно находится иголка, но как только вы ее нащупаете, не останется никаких сомнений, что вы ее нашли! Взломщик может долго возиться с сейфом, пробуя одну комбинацию за другой, но, как только комбинация окажется правильной, дверь тут же откроется.

У задач об иголке в стоге сена, или, если использовать их официальное название, NP-полных задач, есть одно довольно необычное свойство. Может показаться, что каждая из них требует своей, индивидуальной стратегии поисков алгоритма, который позволит решать ее за кратчайшее возможное время. Однако, если будет открыт алгоритм полиномиального времени, находящий кратчайший маршрут по любой карте, с которой может столкнуться пресловутый коммивояжер, это будет означать, что такие алгоритмы гарантированно существуют и для всех остальных таких задач. Хотя бы это дает шорткат к решению задачи поиска шорткатов. Если обнаружится, что существует шорткат к решению какой-нибудь из задач нашего списка, его можно будет преобразовать в шорткат к решению любой другой. Толкин сказал бы, что это один шорткат, чтоб все решить.

Я могу дать вам подсказку, которая показывает, почему это так: посмотрите, как некоторые из задач, которые я описал, можно преобразовывать друг в друга. Возьмем, например, задачу о расписании уроков. Там есть уроки, временные отрезки и накладки, которых необходимо избегать. Используя эту информацию, можно построить сеть, в которой каждый урок будет обозначен точкой, а накладки – линиями, каждая из которых соединяет два урока, между которыми возникает противоречие. Тогда распределение уроков по временным отрезкам превратится в задачу, точно совпадающую с задачей о раскрашивании точек графа таким образом, чтобы никакая линия не соединяла две точки одного и того же цвета.

Использование отсутствия шорткатов

Бывают такие ситуации, в которых важно, чтобы никаких шорткатов не было. Например, разработка нераскрываемых шифров. Разработчикам шифров выгодно такое положение вещей, когда взломать зашифрованное сообщение бывает, по-видимому, невозможно без полного перебора всех возможных вариантов. Взять, к примеру, кодовый замок. Если у него есть четыре колесика, на каждом из которых по десять цифр, то, чтобы его открыть, нужно перебрать 10 000 разных чисел, от 0000 до 9999. Некачественно изготовленные замки иногда выдают то положение, в котором замок открывается, потому что при установке правильной цифры в механизме замка происходит физический сдвиг, но в общем случае у взломщика нет никакого шортката, кроме перебора всех комбинаций.

Однако в других шифровальных системах обнаруживаются слабые места, которые можно использовать для создания шорткатов. Вот, например, классический «шифр Цезаря», он же шифр подстановки. Это код, в котором одни буквы алфавита систематически заменяют на другие. Например, каждая встречающаяся в сообщении буква А заменяется какой-нибудь другой буквой – скажем, буквой G. Затем все буквы B заменяются на одну из оставшихся букв. Таким образом, каждая из букв алфавита становится другой буквой. Разных шифров такого рода очень много. Существуют 26! (1 × 2 × 3 × … × 26) разных способов перестановки букв алфавита[126]. (В некоторых перестановках какая-нибудь буква может оставаться той же: например, буква Х заменяется на Х. Интересный вопрос: сколько существует шифров, в которых изменяются все буквы?) Чтобы стало понятно, о какой величине идет речь, заметим, что 26! секунд – это время, еще не прошедшее с момента Большого взрыва.

Если хакер перехватит закодированное сообщение, ему придется перебрать огромное количество разных комбинаций, чтобы его расшифровать. Но у этого шифра есть слабое место, которое обнаружил живший в IX веке ученый-энциклопедист Якуб аль-Кинди: некоторые буквы встречаются в текстах чаще, чем другие. Например, в любом тексте на английском языке чаще всего – в 13 процентах случаев – встречается буква e; второе место занимает буква t с 9 процентами[127]. Кроме того, у букв бывают индивидуальные характеристики, отражающиеся в тех сочетаниях, в которых они обычно используются. К примеру, после буквы q всегда идет u.