Кто из нас не хочет стать миллионером? Ну, разве что миллиардеры. Расскажем, как заработать миллион… решив задачу по математике! Сделать это будет сложно. Но если всё-таки получится, не сомневайтесь: ваше имя будет вписано в историю наравне с Пифагором, Эйлером и Гауссом.
Математика за деньги
Таких «высокодоходных» задач, кстати, несколько. Математический институт Клэя (США) составил список проблем тысячелетия и готов платить по миллиону долларов за решение каждой. Всемирная слава в качестве бонуса тоже гарантирована. Что же это за задачи такие? Очевидно, невероятно трудные — настолько, что у неспециалистов могут возникнуть проблемы даже с пониманием условия. Например, гипотеза Римана гласит:
«Все нетривиальные нули дзета-функции имеют действительную часть, равную 0,5».
При этом, даже если вы поймёте формулировку и сможете доказать гипотезу, не так-то просто будет найти ей применение в жизни. Поэтому мы предлагаем заняться доступной для восприятия проблемой, решение которой может иметь колоссальное практическое значение. Речь о так называемой задаче P = N P (читается как «пэ равно эн-пэ»). Проблема сформулирована следующим образом:
Верно ли равенство P = N P или нет?
Для начала давайте выясним, что такое P и NP.
Простые задачи P
Компьютеры сегодня решают всё больше и больше задач, а значит, растёт количе- ство вычислений и потребность в пере- боре вариантов. Однако есть вычисления, с которыми не справятся даже самые мощные машины. Например, нет смысла спрашивать:
«Является ли заданное число X простым?»
Для сравнительно малых чисел сущест- вует несложный алгоритм, основанный на переборе вариантов. Допустим, необ- ходимо определить, простое ли число 173. Для этого достаточно перебрать все простые числа на предмет того, являются ли они делителями 173. 2 — нет, 3 — нет, 5 — нет и т. д. Можно перебирать таким образом аж до 173 — или догадаться, что если до 13 включительно делителей нет, то и дальше не будет, ведь если бы вдруг нашёлся делитель k числа 173, который больше 13, то число n = (173 ÷ k) тоже было бы делителем 173. Но мы предпо- ложили, что k > 13, значит, n < 173 ÷ 13 < 14, а ведь до 13 включительно делителей нет! Получили противоречие.
Итак, задача поиска делителя не так уж сложна, когда число маленькое. А если оно, например, тысячезначное? Тогда предстоит перебрать огромное количество вариантов. Более того, даже проверка, делится ли заданное тысячезначное число на, скажем, стозначное, — отдельная большая проблема. Забегая вперёд, от- метим, что с задачей поиска делителя у действительно больших чисел пока не может справиться ни один компьютер, и на этом основана почти вся современная криптография. Однако некоторые задачи он не просто решает, но делает это быстро. Какие именно?
В теории алгоритмов есть такой термин — полиномиальное время (от слова «полином» — многочлен). Например, чтобы сложить два n-значных числа, нужно сделать n сложений, а чтобы перемножить два n-значных числа, нужно сделать n2 умножений. Вспомните, как вы умножаете в столбик: сначала первое число из n цифр умножается на последнюю цифру второго числа (n умножений), потом — на вторую и т. д.
Всего будет n + n + … + n (n слагаемых) умножений, то есть n2 действий. Конечно, потом числа надо сложить — это даёт нам ещё несколько раз по n сложений, но так или иначе получается многочлен, зависящий от n. Значит, задачи умножения и сложения чисел полиномиальные, или, как говорят математики, принадлежащие классу P (polynomial — полиномиальный). Иными словами, это класс задач, которые решаются относительно быстро и не становятся намного сложнее при увеличении данных, например цифр в числе.
Сложные задачи NP
Но есть задачи, которые так легко не решить. Например, разбиравшаяся выше задача об определении простоты (поиске делителей) данного числа. Не придумали ещё полиномиаль- ного алгоритма её решения. При этом делитель можно просто «угадать» и проверить, подходит ли он. А деление пусть даже большого числа на другое большое — вполне себе полино- миальная задача. Что же получается? Найти делитель за полиномиальное время мы не можем (по крайней мере, пока), но если повезёт, успеем проверить, является ли верным конкретное решение. Это и есть NP (non-deterministic polynomial) задача.
А что на практике?
Давайте немного отвлечёмся и рассмотрим пример, с которым вы, возможно, сталкивались. Класс пишет контрольную работу, одно из заданий которой — доказать, что число 323 не простое. Отличница Мария умеет решать такие задачи: она последовательно проверяет простые числа на предмет того, являются ли они делителями 323, и в конце концов доходит до числа 17 — ура, получилось! Светясь от счастья, Мария записывает ответ. А другие ученики? Увы, непоседа Алмас не знает, как решать такие за- дачки. Но понимает, что нужно найти какой-нибудь натуральный делитель 323, отличный от 1 и 323. Алмас думает: «Какое бы число выбрать… О! У меня же день рождения семнадцатого, попробую!» Он пробует — и… бинго! 323÷17 = 19.
Решил ли Алмас задачу? Да, как и Мария. Решит ли он анало- гичную задачу? Только если снова повезёт. Однако бывают задачи, в которых не помогает даже везение: проверка оказывается неподъёмной. Например:
«Существуют ли значения параметра a, при которых уравнение x5 + 3×2 + ax + 1 = 0 имеет 3 корня?»
Даже если бы Алмас угадал искомое значение a, ему бы это мало помогло, ведь дальше придётся решать уравнение пятой степени, с чем он вряд ли справится. А вот другой пример NP-проблемы — так называемая задача коммивояжёра.
Предположим, есть несколько городов, соединённых между собой авиарейсами. Коммивояжёр должен побывать в каждом городе по разу, потратив на перелёты наименьшую сумму денег — например, меньше заданной. Требуется найти оптимальный маршрут.
Решить такую задачу перебором крайне сложно при большом количестве городов. Действительно, если их 1000, у коммивояжёра, стартующего из определённого города, есть 999 вариантов, куда лететь в первую очередь. Для каждого из них — 998 точек, куда можно направиться дальше, и т. д. Как вы понимаете, в итоге получается 999! вариантов (факториал, то есть произведение всех натуральных чисел от 1 до 999). При этом любой конкретный маршрут легко проверяется: мы просто складываем суммы за каждый перелёт и сравниваем в конце с искомой.
В общем, если нам повезёт, решить задачу коммивояжёра можно полиномиально, но если не повезёт — увы. Пока, как мы уже говорили, полиномиальный алгоритм не придумали. Так что и эта задача относится к классу NP. Итак, мы выяснили, что есть класс задач P, которые решаются за полиномиальное время, и есть класс задач NP, которые за полиномиальное время проверяются. И вот, как говорят в известном телешоу, вопрос на миллион: совпадают ли эти классы задач? Верно ли, что P = NP?
Суть проблемы
Ответов на этот вопрос может быть больше двух. В ходе опроса, проведённого недавно среди ста учёных, 61 человек сказал, что «не равны», 9 — что «равны»; 8 считают, что гипотеза не выводится из текущей системы аксиом, а значит, не может быть доказана или опровергнута; 22 затруднились с ответом. В чём же проблема и как вообще можно доказать, что эти классы равны или не равны?
Для начала заметим, что класс NP полностью включает в себя класс P. Действительно, если вся задача выполняется за полиномиальное время, то уж проверка конкретного решения тем более не выходит за эти рамки. А вот наоборот… Верно ли, что любая задача, решение которой можно проверить за полиномиальное время, имеет сравнительно быстрое, «полиномиальное» решение? Ведь если мы не можем придумать быстрое решение, чтобы найти делитель, из этого ещё не следует, что такого решения не существует!
Но если кто-нибудь когда-нибудь докажет, что задачу поиска делителя не решить за полиномиальное время, мы получим, что NP не равно P, поскольку эта задача относится к первому классу и не относится ко второму. Что ж, с проблемой разобрались, осталось понять, почему это так важно. Как вы помните, на NP-алгоритмах строится практически вся современная криптография.
Взломать такие коды не получается, потому что задачи декодирования не имеют быстрых решений. Но если кто-то докажет, что P = NP, все информационные системы (включая банковскую) окажутся под угрозой, ведь это будет означать, что для задачи декодирования есть быстрый, полиномиальный алгоритм.
