Поговорим о сложности. Немного вышедшая из моды тема "P vs NP ". О чем же идет речь?
Многие задачи сводятся к перебору на конечном множестве. Скажем, поиск или сортировка. И разные алгоритмы имеют различную сложность, то есть число операций из заданного набора допустимых операций. Например, команд процессора или (в случае сортировки) сравнений. Вот есть сортировка методом пузырька: каждый элемент сравнивается с соседними и меняется с ними местами, если надо. Как бы всплывает. А есть более эффективные алгоритмы, например QuickSort.
В чем идея QuickSort? Выберем элемент, можно даже случайно, и побросаем те элементы, что больше, вправо, а те, что меньше — влево. А потом правую и левую часть отсортируем тем же способом. Ясно, что это эффективнее пузырька.
Но конечное множество для перебора часто не дано сразу, а получается комбинаторно из условий задачи. В той же сортировке мы перебираем, по сути, различные перестановки элементов массива длины n, а их n! (факториал, который очень быстро растет). То есть задача описана компактно, одним числом n, а переборное множество очень велико, и полный перебор очень неэффективен. Но и не нужен, так как есть алгоритмы намного более эффективные. Даже если они тоже переборные.
Вот такие задачи, в которых число операций задано как некоторая степень длины входа, они полиномиальные, или из класса Р. Можно сказать, что сортировка полиномиальна, так как длина входа порядка n, а решается, даже пузырьком, за число операцией порядка n².
Есть задачи, которые точно не Р. Например, у вас есть n подчиненных и вам надо выбрать из них группу. Эффективность группы можно проверить только тренировкой. Получается полный перебор всех подмножеств, а это экспоненциальная сложность.
Приведем несколько примеров классических задач.
- Задача коммивояжера (ЗК): дан список из n городов и цены на билеты между ними. Нужно составить кольцевой маршрут, посещающий каждый город по одному разу и при этом кратчайшей длины. Предполагается обычно, что надо вернуться в исходный город и это повторным посещением не считается. В варианте распознавания: имеется ли маршрут дешевле заданного порога С? По сути, надо выбрать перестановку порядка посещения городов, на которой достигается минимум.
- Выполнимость: дана логическая формула в виде произведения сумм термов, где термом называется логическая переменная или ее отрицание, умножение — операция И, а сложение — ИЛИ. Сложение отличается от обычного только правилом 1+1=1. Может ли эта формула быть истинной при каком-то наборе переменных? Например, формула (x+y)(!y+!z), где восклицательный знак означает отрицание, истинна при x=1 и y=0. А вот формула (x+y)(!x+y)(!y) всегда ложна.
- Линейное программирование: Даны линейные ограничения вида ax≤b, где a, b, x — векторы. И функция cx. Найти максимум функции. Или выяснить, может ли эта функция принять значение больше С.
- Простое число: выяснить, просто ли данное число.
- Факторизация: разложить произведение двух простых чисел на множители. Или выяснить, разлагается ли.
Если не все города связаны маршрутами, до ЗК может вообще не решаться: например, если во все города летают рейсы только из Москвы. Зато если транзит не считать за посещение города, то такая задача становится тривиальной, так как все маршруты равны. ЗК в класс Р (пока) не входит. Но что интересно, задача поиска хотя бы одного маршрута сама по себе сложна: не Р (пока).
Задача выполнимости кажется банальной, так как можно раскрыть скобки и получить сумму произведений. Если хоть одно слагаемое останется, то формула выполнима. Но раскрытие скобок (каждый с каждым) оказывается сложной процедурой. Пример: (x + !y)(!x + z)(y + !z), где !x — отрицание. Задача в Р (пока) не входит. Если слагаемых в каждой скобке не более двух, задача полиномиальна.
Решение задачи Линейного программирования достигается в вершине многогранника, образованного плоскостями, которые задают ограничения. В этом смысле она переборная. Как оказалось, она Р.
Задача "Простое число" тоже Р, как оказалось. Но не факторизация (разложение на простые множители). Пока.
Теперь NP. Все задачи можно поставить в форме распознавания: да или нет. Бывает так, что ответ "да", и можно предъявить некий объект полиномиального размера (удостоверение), и имеется полиномиальный алгоритм, который на этом объекте дает "да". Иными словами, можно полиномиально проверить, что ответ "да". А если ответ "нет", то ничего не предполагается.
Скажем, найти маршрут дешевле С в задаче коммивояжера мы пока полиномиально не можем. Если не повезет, придется перебирать почти все маршруты. А вот проверить предъявленный маршрут можем вполне и это недорого: просто сложить цены на перелеты один раз.
Имея набор переменных (какие истинны, какие ложны) для задачи Выполнимость, можно подставить их в формулу и проверить, что получается истина.
Имея значения переменных, можно проверить и задачу линейного программирования: все ограничения должны быть удовлетворены и функция больше порога. Имея простые множители, можно перемножить их и посмотреть, получилось ли исходное число.
Чуть хитрее с проверкой на простоту числа. Предъявляется доказательство простоты. Упрощая, объясню так: число простое, если не делится ни на какое число, кроме 1 и себя. То есть "в лоб" надо пробовать делить на 2, 3 и так далее до n-1. Но можно же проверить только простые числа, меньшие корня из n (включительно). Вот если их предъявить, то это и будет проверяемое доказательство. Правда, чисел этих все равно многовато, так что всё сложнее, но смысл вы поняли.
Класс задач, которые полиномиально проверяемы, и есть класс NP.
Ясно, что NP включает Р, так как если решать можно, то проверить тем более. Задача на миллион — установить, совпадают ли эти классы или всё-таки NP>P.
Казалось бы, вот задача на подбор группы подчиненных. Она точно не Р, ибо принципиально требует перебора всех подмножеств. Но ведь можно предъявить хорошую группу и проверить за одну тренировку! Всё? Мы решили проблему тысячелетия? Нет. Есть подвох. Как мне кажется, он в том, что удостоверение должно быть полиномиального размера. Число подчиненных n, а задать подмножество — это уже требует указания функции на всех числах от 1 до n со значениями 0 и 1. Это n бит, а само число кодируется логарифмом: log2n бит достаточно. То есть, удостоверение не полиномиально.
Гипотеза P=NP по сути утверждает, что если задачу можно "дешево" проверить, то ее можно и "дешево" решить. Дешево — это полиномиально, то есть без полного перебора.
Простота числа и линейное программирование оказались Р-задачами, что обнадеживает. Причем алгоритмы непереборные.
Плохая новость: полиномиальные алгоритмы мало что дают на практике. Для малых размерностей выгоды нет, а для большой эффективнее другие методы. Могу ошибаться, но вроде как только философский комфорт принесли эти результаты.
Более того, доказано, что переборный алгоритм не может в общем случае быть полиномиальным. То есть поиск в этом направлении и не мог привести к успеху.
Есть NP-полные задачи, а которым полиномиально сводится любая NP-задача. Если решить NP-полную задачу полиномиально, то проблема будет решена.
Любопытно, что линейное программирование тоже является NP-полной задачей. Но в другой постановке, а перевод из одной формы в другую полиномиально (пока) не делается.
Лично я считаю, что P=NP. Аргументы в другой раз приведу.
Посмотрим...
