Что P = NP? И почему это такой известный вопрос?

Чтобы дать самый простой ответ, который я могу придумать:

Предположим, у нас есть проблема, которая требует определенного количества входных данных и имеет различные потенциальные решения, которые могут или не могут решить проблему для заданных входных данных. Логическая головоломка в журнале головоломок может быть хорошим примером: входные данные - это условия («Джордж не живет в синем или зеленом доме»), а потенциальное решение - это список утверждений («Джордж живет в желтом доме»). дом, выращивает горох, владеет собакой »). Известным примером является задача коммивояжера: учитывая список городов и время, необходимое для того, чтобы добраться из любого города в любой другой, а также ограничение по времени, потенциальным решением может быть список городов в том порядке, в котором их посещает продавец, и это сработает, если сумма времени в пути будет меньше установленного срока.

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

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

Следовательно, проблема P = NP может быть выражена следующим образом: если вы можете эффективно проверить решение проблемы описанного выше типа, сможете ли вы найти решение (или доказать, что его нет) эффективно? Очевидный ответ: «Почему у вас должна быть такая возможность?», И именно в этом суть дела сегодня. Никто так или иначе не смог это доказать, и это беспокоит многих математиков и компьютерных ученых. Вот почему любой, кто сможет доказать решение, получит миллион долларов от Claypool Foundation.

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

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

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

Краткое изложение моих скромных знаний:

Есть несколько простых вычислительных задач (например, поиск кратчайшего пути между двумя точками на графике), которые можно вычислить довольно быстро (O (n ^ k), где n - размер входных данных, а k - константа (в в случае графов это количество вершин или ребер)).

Другие проблемы, такие как поиск пути, который пересекает каждую вершину в графе или получение закрытого ключа RSA из открытого ключа, сложнее (O (e ^ n)).

Но CS говорит, что проблема в том, что мы не можем `` преобразовать '' недетерминированную машину Тьюринга в детерминированную, однако мы можем преобразовать недетерминированные конечные автоматы (например, синтаксический анализатор регулярных выражений) в детерминированные (ну, вы можно, но машина будет работать долго). То есть мы должны попробовать все возможные пути (обычно умные профессора CS могут исключить несколько).

Это интересно, потому что никто даже не имеет представления о решении. Некоторые говорят, что это правда, некоторые говорят, что это неправда, но единого мнения нет. Еще один интересный момент - это решение может быть вредным для шифрования с открытым / закрытым ключом (например, RSA). Вы можете сломать их так же легко, как сейчас создается ключ RSA.

И это довольно вдохновляющая проблема.

Я не так много могу добавить к части вопроса, что и почему в части P =? NP, но это касается доказательства. Доказательство не только стоит дополнительной оценки, но и решит одну из Проблемы тысячелетия. Недавно был проведен интересный опрос, и опубликовал результаты (PDF) определенно стоит прочитать в отношении предмета доказательства.

Для начала несколько определений:

• Особая проблема заключается в P, если вы можете вычислить решение за время меньше n^k для некоторого k, где n - размер входных данных. Например, сортировка может быть выполнена в n log n, что меньше n^2, поэтому сортировка выполняется за полиномиальное время.

• Проблема в NP, если существует k такое, что существует решение размером не более n^k, которое вы можете проверить вовремя не более n^k. Возьмем трехкратную раскраску графов: для данного графа трехкратная раскраска представляет собой список пар (вершина, цвет), который имеет размер O(n), и вы можете вовремя проверить O(m) (или O(n^2)), все ли соседи имеют разные цвета. Таким образом, граф можно раскрасить в три цвета только при наличии короткого и легко проверяемого решения.

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

Обратите внимание, что P является подмножеством NP: если вы можете найти решение за полиномиальное время, есть решение, которое можно проверить за полиномиальное время - просто убедитесь, что данное решение совпадает с тем, которое вы можете найти.

Почему интересен вопрос P =? NP? Чтобы ответить на этот вопрос, сначала нужно увидеть, что такое NP-полные проблемы. Проще говоря,

• Проблема L является NP-полной, если (1) L находится в P и (2) алгоритм, который решает L, может использоваться для решения любой проблемы L 'в NP; то есть, учитывая экземпляр L ', вы можете создать экземпляр L, у которого есть решение, тогда и только тогда, когда у экземпляра L' есть решение. Формально говоря, каждая проблема L 'в NP сводится к L.

Обратите внимание, что экземпляр L должен быть вычислимым за полиномиальное время и иметь полиномиальный размер, равный L '; Таким образом, решение NP-полной задачи за полиномиальное время дает нам решение за полиномиальное время для всех NP-задач.

Вот пример: предположим, мы знаем, что 3-раскраска графов - это NP-сложная задача. Мы хотим доказать, что определение выполнимости булевых формул также является NP-трудной задачей.

Для каждой вершины v имейте две логические переменные v_h и v_l и требование (v_h или v_l): каждая пара может иметь только значения {01, 10, 11}, которые мы можем рассматривать как цвет 1, 2 и 3.

Для каждого ребра (u, v) необходимо, чтобы (u_h, u_l)! = (V_h, v_l). Это,

not ((u_h and not u_l) and (v_h and not v_l) or ...) перечисление всех одинаковых конфигураций и оговорка, что ни одна из них не соответствует действительности.

AND 'объединение всех этих ограничений дает логическую формулу, которая имеет полиномиальный размер (O(n+m)). Вы можете проверить, что для вычисления также требуется полиномиальное время: вы делаете простые O(1) вещи для каждой вершины и каждого ребра.

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

Следовательно, если 3-раскраска графов NP-полная, то выполнимость булевой формулы также является выполнимостью по логическим формулам.

Мы знаем, что 3-раскраска графов NP-полна; однако исторически мы узнали это, сначала показав NP-полноту выполнимости логической схемы, а затем уменьшив ее до трехцветности (а не наоборот).