≠ Собирай рюкзак по алгоритму, если будет NP=P
Всем привет! Представьте себе, что вы задумались поиграть в Тетрис, но поиграете в таком режиме бога. Вы знаете, какие фигурки дальше будут падать, в каком порядке, и вы хотите продумать некий алгоритм, как бы набрать побольше очков, чтобы скинуть больше рядов и чтобы вас не завалила. Понятно, что для человека это слишком сложная задача. Перебор с скачками большого количества вариантов. Выясняете, что даже компьютер решить её быстро не может.
Что значит "быстро"? Давайте разбираться.
Dealer Rival Sons, я приветствую вас на канале QWERTY. Не забываем подписываться те, кто это вдруг ещё не сделал. И сегодня мы с вами поговорим про сложности задач, в частности обсудим так называемые P и NP задачи.
О чем пойдет речь? Ну вот возьмем какую-нибудь не трудную задачу, например, сложение двух чисел, каждый из которых n-значное. Ну, скажем, 10 изнаночных 20-значных. Сколько операций нам потребуется, чтобы выполнить это сложение? Все вы умеете складывать.
Столбик, последнюю цифру с последней, предпоследний с предпоследним и так далее. m сложений. Правда, ещё какие-то период перехода через десяток. Ну, короче говоря, если у меня увеличивается длина числа на сколько-то символов, вот примерно настолько же операции увеличиваются.
Сложение, то есть сложности этого алгоритма - оно порядка m. То есть такой же, как длина числа. Если вдруг мы возьмем умножение, там, как вы помните, каждую цифру 2 числа надо умножить на каждую цифру 1. Итого: первую цифру n, вторую t.n. и так далее, n квадрат. Плюс ещё какие-то сложения там в конце и так далее.
Так или иначе, общее количество операций в зависимости от этой длины числа n будет многочленом. Сколько там - квадрат плюс сколько-то. То есть в таком случае сложность вот этого моего алгоритма умножения чисел длиной n - она многочлен или полином, как его ещё называют.
Такую сложность также называют полиномиальной, а задачи, которые решаются вот такой полиномиально, называют задачами класса P. P - это над соло полином.
То есть ещё раз, о чем идет речь? Если мы увеличиваем вот этот размер входных данных, сложность того алгоритма, который мы решаем задачу, она увеличивается в виде многочлена. То есть по формуле какой-нибудь там сколь в виде будь он в какой-то степени плюс когтем в какой-то степени, в степень это натуральные числа.
Например, то вот такая задача называется полиномиальной или задачи класса P.
Не сложно понять, что если есть задачи класса P и есть задачи NP, действительно. Если мы возьмем задачу коммивояжера (это слово уже несколько отживает, поэтому можно заменить на задачу путешественника), это классическое название. В чем оно заключается?
Есть несколько городов, и какому-то человеку нужно посетить все эти города, но потратив минимальное количество денег, например, на перелеты. Мы в Берлине, Братиславе, да, да, тесьма. Или если вы не любите летать на самолетах, считаете, что он едет на машине, ему надо потратить меньше денег на бензин. Более того, я могу сформулировать задачу чуть попроще: можно ли ему построить такой маршрут, чтобы он потратил на бензин, допустим, там меньше ста тысяч рублей при фиксированных городах, фиксированные там расстояния, и мы знаем, сколько стоят по бензину, проехать от одного города до другого для каждой пары городов?
Вот оказывается, что перебор вариантов на такой задачи - он не полиномиальный. С другой стороны, если мы захотим проверить конкретное решение, то есть выбор конкретного маршрута, и мы проверим: а там меньше ста тысяч или больше? Такая проверка, конечно, она довольно быстрая, она полиномиальна.
И вот задачи, которые пока, по крайней мере, мы не понимаем, решаются за полиномиальное время или нет. Но мы точно понимаем, что проверка конкретного решения занимает полиномиальное время. Вот такие задачи называются NP-неподдающимися, ну, или по-другому, NP-доказуемыми.
То есть, переводя на русский, возможно, они полиномиальные, а может, быть и нет. И вот теперь, собственно, вопрос, который назван проблемой тысячелетия: а вот эти классы P - то есть задачи, которые решаются за полиномиальное время, и NP - то есть про которые мы знаем, что проверка-то полиномиальная, но алгоритм полиномиальный мы пока думать не можем для решения всех задач.
Вот эти классы совпадают или нет?
Несложно понять, что класс P включается в класс NP. Если уж мы можем за полином решить всю задачу, то уж проверить - мы точно можем.
А вот наоборот, в этом вся и соль! И на самом деле вам может показаться, что какая-то заумная математическая муть, кому-то это надо, каким-то конкретным ученым. Ничего подобного. Если вдруг когда-нибудь мы сможем показать, что классы совпадут, и более того, найдем какой-нибудь хороший полиномиальный алгоритм для решения неполиномиальных вот этих не детерминированных полиномиальных задач, то на этом полетит вся конфиденциальность ваших данных: ваши банковские карточки, ваши аккаунты в соцсетях и так далее.
Потому что сейчас большинство алгоритмов, которые шифруют данные, они как раз основаны на том, что проверять их довольно просто, а расшифровать из разгадать долго. При увеличении вот этих самых данных, если мы придумаем какой-то короткий алгоритм, то всё. Более того, есть такое понятие, как NP-Полные задачи.
То есть такие задачи, к которым сводятся любая задача вида NP за полиномиальное время. То есть это значит, мы не все задачи должны решать, а вот конкретную одну NP-полную, скажем, задачу коммивояжера, она является полной. Если мы покажем, что она принадлежит к P, мы таким образом решим все возможные NP задачи, и это довольно круто.
А вот ещё пример. Такой вот NP-задачи: представьте себе, что у вас есть рюкзак. В этом рюкзаке, яну, есть какая-то вместимость предельная, допустим, в килограммах он выдержит топ 100 килограмм. Есть набор вещей, каждая вещь сколько-то весит и сколько это стоит. Все вещи в рюкзак не влезут.
Вот какие вещи надо взять, чтобы вы могли внести максимальную стоимость, даже как можно более ценная сумма прочего. Эта задача тоже переборная, и, как задача коммивояжера, она не является полиномиальной. По крайней мере, пока никто не знает полиномиального алгоритма для игорь ошейник.
Так что на самом деле такие задачи встречаются сплошь и рядом, и практически любая задача оптимизации, которую вы не возьмете, она тоже в районе вот этого NP. Если мы сможем решить какую-нибудь полную задачу, значит, решим и всех.
Забавный момент: учёные, они сами до сих пор не то что не решили, они даже не знают точно, не уверены, какой ответ будет в этой задаче: равны P и NP или нет.
В частности, не так давно был проведён опрос 100 человек, 100 ученых, известных: как они считают? Вот да или нет, можно ли доказать, что P равно NP? Тоже может быть это вообще не верно. Вот оказалось, что 61 человек из ста считает, что это не верно, то есть что существуют такие задачи NP, которые не являются полиномиальными. Правда, пока вот это не доказано.
Есть те, кто считает, что да, верно, что совпадут, и рано или поздно мы это докажем. Есть немалая доля тех, кто затруднились ответить, но особенно интересно, что есть несколько человек, которые сказали, что это доказать невозможно в принципе. То есть нашими нынешними методами мы не можем строго доказать, равны P и NP или нет.
Вот это, по-моему, довольно интересно!
Ещё раз напоминаю, что наш канал QWERTY - вот он, и подписаться на него можно здесь. Ну, а вам я желаю по возможности решить задачу вида P равно NP. Потому что, помимо того что круто, сделаете для всей математики, решив задачу тысячелетия, вас ждет премия, как и господину Перью Манн. Надо за решение супер-сложной задачи - миллион долларов!
Всем до встречи на нашем канале. Пока-пока! Елена. [Музыка]