уже вовсю полыхал ранний июньский рассвет. Дима объявил, что будет воспитывать Таню в рыночном духе, и на этой бодрой ноте побежал к открывшемуся метро. А Таня предпочла вообще не ложиться – надо было готовиться к экзамену по матану.

Когда сессия осталась позади, она решила потратить лето на работу в ВЦ. Там у нее появился свой стол и время на ЭВМ. Марков давно понял, что программирование, которое Таня освоила стремительно, превратилось для девушки в рутину, и предложил ей самой выбрать тему. И Таня вместе с Сашей, писавшим диссертацию, утонула в институтской библиотеке. Теперь ее интерес полностью сосредоточился на Курте Гёделе, доказавшем в 1931 году две знаменитые теоремы о неполноте.

Гений из Австрии продемонстрировал, что кажущееся ослепительно ясным математическое знание не может достичь одновременно и полноты, и непротиворечивости. В любой математической теории, основанной на формальной арифметике, которая является разделом математической логики, в отличие от школьной арифметики, всегда можно сформулировать некое утверждение, которое будет истинно, но недоказуемо. Таким образом, или мы сумеем описать весь мир в математических терминах, утверждал Гёдель, но тогда это знание будет изобиловать необъяснимыми парадоксами, или будем стремиться к отсутствию противоречий, но тогда знание не будет полным.

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

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

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

Решение задачи и проверка полученного решения суть две разные и в равной степени важные процедуры.

Фишка в том, что время и трудоемкость проверяющей процедуры может сильно отличаться от времени и трудоемкости самого процесса решения. Проверить решение иногда очень просто. А вот решить задачу алгоритмически, то есть найти точный пошаговый способ решения, который определен однозначно, завершается за конечное время и выдает правильный результат, может оказаться сложно. В 1930 году австриец Карл Менгер придумал знаменитую задачу коммивояжера, которая относится как раз к этому типу NPполных задач. Смысл задачи в том, что условный коммивояжер должен найти самый короткий маршрут между несколькими городами так, чтобы через каждый город он проезжал только один раз и в итоге вернулся в исходную точку. Если речь идет о трех – пяти городах, это проще простого. Но по мере увеличения числа городов решение будет усложняться в геометрической прогрессии. Для пятнадцати городов существует сорок три миллиарда маршрутов, а для восемнадцати их уже сто семьдесят семь триллионов. При этом, если решение уже найдено, проверить его корректность легко – достаточно убедиться, что все заданные точки пройдены по одному разу.

И вот тут математики приходят в отчаяние. Задачато примитивная! Но единственный возможный способ ее решения – старый добрый перебор. Слишком простой и слишком трудоемкий.

Этот факт приводит математиков в ярость уже пятьдесят лет и наводит на мысль, что для облегчения судьбы коммивояжера существует – должен существовать! – другой алгоритм, куда более эффективный. Благодаря скромному коммивояжеру наука обогатилась несколькими новыми направлениями, но к лету 1988го основным методом решения этой задачи так и остался все тот же перебор.

Задачи, которые решаются относительно быстро, математики относят к классу сложности P. Задачи же, решение которых, как в случае коммивояжера, проверяется за полиномиальное время, относят к классу NP. Понятно, что все задачи класса P войдут и в класс NP. Вопрос в другом. Пример с коммивояжером показывает, что существуют задачи, которые принадлежат к классу NP (легко проверить), но не принадлежат к классу P (легко решить). Выходит, что, если никакого иного алгоритма решения задачи коммивояжера, кроме перебора, нет в природе, классы P и NP не равны. Но именно в этом математики и не уверены. Отсутствие иного алгоритма все еще не доказано. Если такой алгоритм будет найден, значит, задача коммивояжера не только легко проверяется, но и легко решается. И классы P и NP равны. Короткая статья Леонида Левина была как раз об этом.

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

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

На этом месте у Татьяны захватило дух. В тишине библиотеки перед ней разверзлось темное пространство неведомого. Она стояла у края человеческого знания. Дальше была территория прорыва, ошибок. Но именно туда ее и тянуло.

Прошлого больше не было. Не было воспоминаний, времени, обид, жалости к себе. С этой нулевой отметки жизнь начиналась заново. Дорога вела в пропасть. Если удастся отодвинуть край этой пропасти хотя бы немного, все будет оправдано. С этой мыслью она побежала к Маркову и вывалила перед ним на стол кипу журналов и собственных записей. Марков проглядел заголовки.

– О, Таня, вы наткнулись на интересную проблему! – воскликнул он. – Но нерешаемую.

– А если всетаки?..

– Тогда пан или пропал, – вздохнул Марков. – Или новый космос, или все попрежнему – потихоньку и помаленьку.

– Я тут прикинула пару вариантов, – пробормотала Таня, – но не выходит.

Марков захохотал:

– Не у вас одной, Танечка! Эту задачу решали великие умы, уж поверьте. И дело даже не в том, что она сложная. Сложных задач много, но это не значит, что они нерешаемы. А здесь все упирается в то, что мы не знаем, решаема она в принципе или нет. Но знаете, что тут важно?

Таня насторожилась.

– Важно понимать, что любой современный математик действует в определенной логике, которой его научили. Как говорят военные, мы всегда готовимся к