Как определить, вычислительная задача сложная или нет? Как это измерить? Вот, например, перемножить два числа — сложно или нет? Зависит от длины числа: двузначные числа перемножить гораздо быстрее, чем 200-значные. Зависит еще от и метода: алгоритмов много разных и постоянно разрабатываются новые, все шустрее и шустрее. Если считать в столбик — цифра за цифрой, — то таких элементарных умножений для умножения двух N-значных чисел потребуется N²; а современные алгоритмы делают это почти линейно — за N∙ln N∙ln(ln N) операций. (Важно еще, какой объем памяти доступен.)
Время работы алгоритма выражают через объем входных данных N. Если зависимость эта похожа на полином: N², N³, или даже N⁴⁵⁶⁷⁸⁹, то задача считается относительно простой, ее относят к классу P (буква P как раз от слова полином).
Класс P входит в NP.
К NP относят задачи, для которых можно быстро проверить имеющееся решение, хотя для поиска этого решения может потребоваться полный перебор всех вариантов. Например, чтобы решить японскую головоломку судоку, нужно перебирать варианты, но зато проверить найденное решение довольно просто. То же и с паззлами — головоломками, где нужно из кусочков собрать картинку. Подбирать кусочек к кусочку — это долго, это переборная задача; а проверить решение можно с одного взгляда.
Если все решения можно найти за полиномиальное время, то и проверить тоже. Поэтому любая задача класса P входит в NP. Но вот верно ли обратное, никто не знает.
Вдруг для задач NP существуют быстрые решения, просто их еще никто не нашел? Ведь если мы не умеем решать задачу быстро, это еще не означает, что быстрого решения нет вовсе. Например, трудно ли определить, составное число или простое? Долгое время не знали, к какому классу эта задача относится, и только в 2002 году индийский ученый Маниндра Агравал и два его студента Каяла и Саксена опубликовали алгоритм, который решает эту задачу за полиномиальное время. Оказалось, что это задача класса Р. Вдруг удастся найти такие алгоритмы для всех задач класса NP?
Что же нас ждет, если мы научимся быстро решать переборные задачи?
Нынешние криптографические методы перестанут защищать нашу информацию в интернете. Но зато появятся новые. Чтобы заказать доставку продуктов, достаточно будет видеозвонка. Ты человеческим голосом рассказываешь, какие продукты тебе нужны, этого достаточно и для идентификации, и для формирования заказа.
Можно будет быстро и очень подробно анализировать ДНК пациента и создавать специально для него лекарства без побочных эффектов. РНК всяких вредоносных вирусов тоже можно будет расшифровывать быстрее, чем они мутируют. Взрывные достижения биоинформатики позволят нам жить дольше и здоровее.
Преступников разыскивать тоже будут быстрее, очень быстро и точно можно будет идентифицировать и цифровые их следы, и биологические. Преступность упадет.
Искусственный интеллект поумнеет. Сейчас мы можем научить его распознавать, сравнивать и воспроизводить речь или картинки. А с новыми алгоритмами он научится смотреть глубже: разберется, что именно привлекает нас в текстах или в музыке, и создаст новые шедевры.
Рекомендательные сервисы вроде яндекс.дзен больше не понадобятся. Алгоритмы научатся писать книги и музыку специально на вкус каждого отдельного читателя...
К счастью, никто не верит, что все так и будет
Все ожидают, что когда-нибудь удастся доказать несовпадение этих классов. Время от времени даже публикуются доказательства. Из серьезных попыток — в 2010 году свое доказательство опубликовал Винэй Деолаликар, а в 2017 году Норберт Блюм. Каждый раз обнаруживаются ошибки, и многие считают, что имеющимися методами доказать несовпадение P и NP не удастся. Для этого понадобятся какие-то новые, пока еще небывалые идеи в теоретической информатике.
Проблема представляется настолько важной, что она вошла и в список задач столетия от Стивена Смейла, и в список задач тысячелетия от института Клэя.
Еще совпадающие задачи из этих списков: