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

Таким незамысловатым способом можно представить себе суть одной из математических задач тысячелетия — задаче равенства классов P и NP. Даже если вы далеки от математики и информатики, я постараюсь рассказать вам об этой задаче так, чтобы вы оценили её изящную сложность. 

Задачи тысячелетия

Чтобы грамотно подступиться к задаче равенства классов P и NP, сперва необходимо сделать небольшое отступление касательно института Клэя и списка из 7 задач тысячелетия.

Математический институт Клэя — это частная некоммерческая организация, которая занимается спонсированием многообещающих математиков и в целом распространением математических знаний. Этот институт известен благодаря публикации списка из 7 задач тысячелетия, каждая из которых представляет собой классическую математическую задачу, которая не решена на протяжении очень долгого времени. Помимо этого, за верное решение любой из 7 проблем объявлено вознаграждение в виде 1 000 000 долларов США. На сегодняшний момент из всего списка решена лишь 1 задача — гипотеза Пуанкаре, решение которой принадлежит российскому математику Григорию Перельману.

Как нетрудно догадаться, равенство классов P и NP является одной из 7 задач в данном списке, что подчеркивает её колоссальную сложность и фундаментальность.

Начнём с алгоритмов

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

Как мы определяем, какой из двух алгоритмов эффективнее? Как правило, нас заботит потребление двух вещей: времени и памяти. Стараясь построить эффективный алгоритм, мы стараемся сделать так, чтобы он потреблял как можно меньше памяти и работал максимально быстро. Эти две вещи зависят от размера входных данных, которые мы подаем алгоритму. 

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

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

Если зависимость времени работы программы от объёма входных данных описывается линейной, квадратичной, кубической и другими функциями, мы говорим о полиномиальном времени работы. Причина довольно-таки простая: линейная, квадратичная, кубическая и так далее функции являются полиномами, то есть многочленами от некоторого числа переменных. Понятие полиномиального времени работы довольно скоро нам пригодится. 

Стоит отметить, что время работы программы может иметь не только полиномиальную зависимость от объема входных данных. Характер роста может быть куда более взрывным. Классический пример: экспоненциальная зависимость, при которой увеличение входных данных всего на 1 единицу измерения повлечёт увеличение времени работы алгоритма в некоторое константное количество раз. 

Опять же упрощая, можно сказать, что полиномиальные алгоритмы — это быстрые алгоритмы, а те же экспоненциальные — нет. 

Переходим к классам задач P, NP и NP-complete

Класс задач P определяется довольно просто — это набор таких задач, для которых мы знаем алгоритм, работающий за полиномиальное время. Для простоты можно считать, что класс P — это класс простых задач, поскольку мы знаем быстрые алгоритмы для их решения. Примеры задач из класса P: сложение двух чисел, сортировка множества из n элементов, поиск элемента в некотором множестве, выяснение связности графа и так далее. 

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

Ещё более сложные задачи — это задачи из класса NP-complete. Если вам удаётся свести решение задачи А к решению задачи Б, то последняя задача как минимум настолько же сложная, как и первая. Суть NP-complete класса в том, что к любой задаче из данного класса можно свести абсолютно все задачи из класса NP, то есть каждая задача из данного класса настолько же сложна, как и любая задача из NP. Примеры задач из класса NP-complete: задача о ранце или та же задача коммивояжёра. 

Равенство классов P и NP

Теперь, когда мы разобрались в понятиях, мы можем сформулировать интересующую нас задачу. Правда, формулировка явно следует из названия: равны ли P и NP? Возможно ли построить для всех задач из NP полиномиальный алгоритм? Другими словами, если мы имеем задачу из класса NP и мы знаем, что для неё можно быстро проверить решение, означает ли это, что данное решение можно столько же быстро найти?

Зачем мы вводили класс NP-complete?

Это связано с одним очень интересным моментом касательно доказательства «P против NP». В классе P содержится огромное количество задач, равно как и в классе NP. Помимо этого, умнейшие учёные компьютерных наук на протяжении десятилетий пытались построить быстрый (полиномиальный) алгоритм хотя бы для одной из многих сотен задач из класса NP. Тем не менее, учитывая, что любая NP-complete задача настолько же сложная, как и все задачи из NP, если хотя бы для одной NP-complete задачи нам удастся доказать, что её можно быстро решить, мы автоматически докажем то же самое для всех задач из класса NP. 

Почему это важно?

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

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

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

Почему это особенно важно для криптографии?

Стоит понимать, что солидная часть криптографии (например, криптографические системы с открытым ключом) строится на предположении, что некоторые вещи нельзя выполнить быстро (чуть более точно: нельзя построить быстрый алгоритм для некоторых задач). Например, быстро разложить число на простые множители. Если выяснится, что P = NP, и мы способны построить быстрые алгоритмы для задач из класса NP (вроде разложения числа на простые множители), то многие методы защиты сразу же устареют, поскольку у каждого желающего будет быстрый алгоритм, способный обойти защиту. 

Так P равно NP или нет?

Большинство современных специалистов сходится во мнении, что P не равно NP. Некоторое интуитивное объяснение этому мы уже давали: на протяжении десятилетий лучшие умы компьютерных наук пытались построить быстрые алгоритмы для задач из классов NP и NP-complete, но это ни разу не увенчалось успехом. Кроме того, в 2002 и 2012 годах было проведено голосование «равны ли P и NP» с четырьмя вариантами ответов: нет, да, не уверен, вопрос независим с современной системой аксиом и поэтому теорему невозможно доказать или опровергнуть. Результаты были следующими (в процентах): 61/83, 9/9, 22/5, 8/3. Другими словами, в рамках последнего голосования 83 процента опрошенных верят, что P не равно NP. 

Вот вы и познакомились с одной из наиболее значимых задач нашего поколения, которая имеет огромный практический вес. Особенно если будет доказано равенство классов P и NP. Впрочем, это, возможно, произойдёт ещё совсем нескоро.