Но эта задача так нравится мне потому, что, когда я был школьником, такой алгоритм существовал. Что же случилось с тех пор? Нет, дело не в том, что мы утратили этот алгоритм, а в том, что изменились правила начисления очков. Раньше команды получали за победу всего лишь по два очка, а в случае ничьей – по одному каждая. Потом решили, что это побуждает футболистов сводить матчи к скучным ничьим. Поэтому в 1981 году было принято решение усилить привлекательность побед для команд. Вместо двух очков победившая в матче команда стала получать три. Это, казалось бы, безобидное новшество резко изменило ситуацию с точки зрения задачи о возможности выхода той или иной команды на верхнюю строчку турнирной таблицы Премьер-лиги.

Важнее всего то обстоятельство, что до 1981 года суммарное число очков, распределяющееся между командами, не зависело от того, кто выигрывает, проигрывает или заканчивает матч вничью. В турнире участвуют 20 команд; каждая из них встречается со всеми остальными по два раза, на своем поле и на выезде, то есть всего получается 20 × 19 матчей. В старой системе в каждом матче разыгрывались два очка, которые распределялись в зависимости от его исхода. Стало быть, суммарное число очков, распределенных между 20 командами к концу сезона, было равно 2 × 20 × 19 = 760.

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

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

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