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

Например, если у вас есть проблема, и кто-то говорит: "Ответом на вашу проблему является набор чисел 1, 2, 3, 4, 5", компьютер может быстро определить, правильный это ответ или нет, но ему может потребоваться очень много времени, чтобы самостоятельно придумать "1, 2, 3, 4, 5". Другой пример - поиск простых чисел. Легко проверить, является ли число простым, но очень трудно найти эти числа в первую очередь. Для некоторых интересных, практических вопросов такого рода нам не хватает способа быстро найти ответ, но если нам предоставлен ответ, то его можно быстро проверить, то есть верифицировать. Таким образом, можно считать, что проблемы NP похожи на загадки: ответ на загадку может быть трудно найти, но как только человек слышит ответ, он кажется очевидным. В этом сравнении (аналогии) основной вопрос заключается в следующем: действительно ли загадки настолько трудны, как нам кажется, или мы что-то упускаем?

Поскольку подобные вопросы P versus NP настолько важны с практической точки зрения, многие математики, ученые и программисты хотят доказать общее утверждение, что любая быстро проверяемая проблема также может быть решена быстро. Этот вопрос настолько важен, что Математический институт Клэя выделит 1 000 000 долларов тому, кто успешно докажет или даст достоверное объяснение, опровергающее это утверждение.

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

Поскольку усилиями ученых и математиков до сих пор не найдены общие, простые методы решения NP-задач, многие считают, что существуют NP-задачи, отличные от P-задач (то есть, что P ≠ NP истинно). Большинство математиков также считают, что это так, но в настоящее время никто не доказал это с помощью строгого математического анализа. Если удастся доказать, что NP и P - одно и то же (P = NP истинно), это окажет огромное влияние на многие аспекты повседневной жизни. По этой причине вопрос о P и NP является важной и широко изучаемой темой.

Предположим, кто-то хочет построить две башни, складывая камни разной массы. Необходимо убедиться, что каждая из башен имеет абсолютно одинаковую массу. Это означает, что камни нужно сложить в две кучи с одинаковой массой. Если вы угадаете, какое деление камней, по вашему мнению, получится, вам будет легко проверить, правильно ли вы поступили. (Чтобы проверить ответ, можно разделить камни на две кучи, а затем с помощью весов проверить, одинаковая ли у них масса). Поскольку эту задачу, называемую компьютерщиками "Разбиение", легко проверить - проще, чем решить ее полностью, как мы увидим, - она не является задачей P. ^[]

Насколько сложно решить эту задачу? Если начать со 100 камней, то существует 2^{100-1}-1 = 633,825,300,114,114,700,748,351,602,687, или около 6.3 x 10^{29} возможных способов (комбинаций) разделить эти камни на две кучи. Если бы можно было каждый день проверять одну уникальную комбинацию камней, это заняло бы 1,3 x 10^{22} или 1 300 000 000 000 000 000 000 000 000 000 000 000 000 000 000 лет усилий. Для сравнения, физики считают, что возраст Вселенной составляет около 1,4 x 10^{10} лет (450 000 000 000 000 000 000 000 000 000 000 000 или около 4,5 x 10^{17} секунд, или примерно на одну триллионную часть больше, чем время, которое потребовалось бы для наших усилий по нагромождению камней. Это означает, что если взять все время, прошедшее с начала существования Вселенной, то для того, чтобы проверить все различные способы разделения камней, необходимо каждую секунду проверять более двух триллионов (2 000 000 000 000 000 000 000) различных способов.

Если запрограммировать мощный компьютер на проверку всех этих способов разделения горных пород, то можно было бы проверить 1 000 000 комбинаций в секунду с помощью современных систем000. Это означает, что000 для проверки всех способов разделения горных пород все еще потребуется 2 000 000}000000 очень мощных компьютеров, работающих с момента зарождения Вселенной.

Однако, возможно, можно найти метод разделения камней на две равные кучи без проверки всех комбинаций. Вопрос "Равно ли P равно NP?" является сокращением вопроса о том, может ли существовать такой метод.

Существует множество важных проблем NP, которые люди не знают, как решить быстрее, чем проверять все возможные ответы. Вот несколько примеров:

• Путешествующий торговый агент хочет посетить 100 городов на автомобиле, начав и закончив поездку дома. У него ограниченный запас бензина, поэтому он может проехать только 10 000 километров. Он хочет знать, сможет ли он посетить все города, не исчерпав запаса бензина.
• В школе 100 различных классов, и учителю необходимо выбрать один час для выпускного экзамена каждого класса. Чтобы предотвратить списывание, все ученики, посещающие один класс, должны сдавать экзамен по этому классу в одно и то же время. Если студент посещает несколько занятий, то все экзамены должны проходить в разное время. Учитель хочет знать, можно ли назначить все экзамены на один день, чтобы каждый ученик смог сдать экзамен по каждому из своих предметов.
• Фермер хочет отвезти на рынок 100 арбузов разной массы. Ей нужно упаковать арбузы в коробки. Каждая коробка может выдержать только 20 килограммов без поломок. Фермеру нужно знать, хватит ли ей 10 ящиков, чтобы перевезти все 100 арбузов на рынок. (Это тривиально, если не более одного арбуза весит более 2 кг, то в каждый ящик можно положить любые 10, если не более десяти арбузов весит более 2 кг, то в каждый ящик можно положить по одному и т.д., для быстрого решения; наблюдение будет ключом к любому быстрому решению, такому как эта задача или задача о наборе чисел).
• В большой художественной галерее много комнат, и каждая стена покрыта множеством дорогих картин. Владелец галереи хочет купить камеры, чтобы следить за этими картинами, на случай, если вор попытается украсть какую-нибудь из них. Он хочет знать, хватит ли ему 100 камер, чтобы убедиться, что каждая картина видна хотя бы одной камере.
• Проблема клики: У директора школы есть список учеников, которые дружат друг с другом. Она хочет найти группу из 10% учеников, которые дружат друг с другом.

В примере выше мы видим, что при {\displaystyle100 100} камнях существует {\displaystyle2100 2^{100}} способов разделить множество камней. При n {\displaystyle n} камнях, существует n2 {\displaystyle 2^{n}} комбинаций. Функция f ( n ) = n2 {\displaystyle f(n)=2^{n}} является экспоненциальной функцией. Она важна для NP, потому что моделирует наихудшее число вычислений, необходимых для решения проблемы, и, таким образом, наихудшее количество времени, которое требуется.

И до сих пор для решения трудных задач требовалось порядка n 2{\displaystyle 2^{n}} вычислений. Для любой конкретной проблемы люди находили способы уменьшить количество необходимых вычислений. Можно найти способ сделать всего 1% от наихудшего числа вычислений, и это сэкономит много вычислений, но это все равно × 0.01( n2 ) {\displaystyle 0.01\times (2^{n})} вычислений. И каждый дополнительный камень все равно удваивает количество вычислений, необходимых для решения проблемы. Есть озарения, которые могут создать методы, позволяющие делать еще меньше вычислений, производя вариации модели: например, n2 / n {\displaystyle3 2^{n}/n^{3}}. . Но экспоненциальная функция по-прежнему доминирует по мере роста n {\displaystyle n}.

Рассмотрим проблему составления расписания экзаменов (описанную выше). Далее предположим, что существует 15000 студентов. Существует компьютерная программа, которая берет расписания всех 15000 студентов. Она работает в течение часа и выдает расписание экзаменов так, чтобы все студенты могли сдать экзамены за одну неделю. Она удовлетворяет множеству правил (никаких экзаменов "спина к спине", не более двух экзаменов в течение 28 часов, ...), чтобы ограничить стресс экзаменационной недели. Программа работает в течение одного часа в середине семестра, и каждый знает свое расписание экзаменов, имея достаточно времени для подготовки.

На следующий год, однако, студентов становится на 10 больше. Если та же программа работает на том же компьютере, то один час превратится в {\displaystyle210 2^{10}} часа, потому что каждый дополнительный ученик удваивает количество вычислений. Это {\displaystyle6 6} недель! Если бы было еще 20 студентов, то

220  {\displaystyle 2^{20}} часов = {\displaystyle1048576 1048576} часов ~ {\displaystyle43691 43691} дней ~ {\displaystyle113 113} лет

Таким образом, для {\displaystyle15000 15000} студентов потребуется один час. Для {\displaystyle15020 15020} студентов, это займет {\displaystyle113 113} лет.

Как видите, экспоненциальные функции растут очень быстро. Большинство математиков считают, что для решения самых трудных задач NP требуется экспоненциальное время.

Математики могут показать, что существуют некоторые NP-задачи, которые являются NP-полными. NP-полную задачу решить по крайней мере так же сложно, как и любую другую NP-задачу. Это означает, что если кто-то нашел метод быстрого решения любой NP-полной проблемы, он может использовать этот же метод для быстрого решения любой NP-проблемы. Все перечисленные выше проблемы являются NP-полными, поэтому если продавец нашел способ быстро спланировать свою поездку, он может рассказать об этом учителю, и она сможет использовать тот же метод для составления расписания экзаменов. Фермер мог бы использовать тот же метод, чтобы определить, сколько коробок ему нужно, а женщина могла бы использовать тот же метод, чтобы найти способ построить свои башни.

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

Основные свойства

В теории сложности вычислений класс сложности NP-полный (сокращенно NP-C или NPC) - это класс задач, обладающих двумя свойствами:

• Она находится в множестве NP (недетерминированных задач полиномиального времени): Любое данное решение проблемы может быть проверено быстро (за полиномиальное время).
• Она также входит во множество NP-трудных задач: Те, которые по крайней мере так же трудны, как самые трудные проблемы в NP. Проблемы, которые являются NP-трудными, не обязательно должны быть элементами NP; более того, они могут даже не быть разрешимыми.

Формальный обзор

NP-полнота - это подмножество NP, множество всех проблем решения, решения которых могут быть проверены за полиномиальное время; NP можно эквивалентно определить как множество проблем решения, решаемых за полиномиальное время на машине. Проблема p в NP также находится в NPC тогда и только тогда, когда любая другая проблема в NP преобразуется в p за полиномиальное время. NP-полная должна была использоваться как прилагательное: проблемы в классе NP-полных были как NP+-полные проблемы.

NP-полные проблемы изучаются потому, что способность быстро проверять решения проблемы (NP), по-видимому, коррелирует со способностью быстро решать проблему (P). Установлено, что каждая проблема в NP быстро решается - так называемое множество проблем P = NP:. Единственная проблема в NP-полном решается быстро, быстрее, чем каждая проблема в NP также быстро решается, потому что определение NP-полной проблемы гласит, что каждая проблема в NP должна быть быстро сводима к каждой проблеме в NP-полном (сводится за полиномиальное время). [1]

Примеры

Известно, что проблема удовлетворительности булевых функций является NP-полной. В 1972 году Ричард Карп сформулировал 21 проблему, которые, как известно, являются NP-полными. Они известны как 21 NP-полная проблема Карпа. Они включают такие проблемы, как проблема целочисленного программирования, в которой применяются методы линейного программирования для целых чисел, проблема ранца или проблема вершинного покрытия.