Предполагая некоторый опыт в математике, как бы вы дали общий обзор теории сложности вычислений наивным?
Я ищу объяснение вопроса P = NP. Что такое P? Что такое NP? Что такое NP-Hard?
Иногда Википедия написана так, как будто читатель уже понимает все вовлеченные понятия.
Hoooo, докторский comp flashback. Хорошо, здесь идет.
Начнем с идеи проблемы решения, проблемы, для которой алгоритм всегда может ответить "да" или "нет". Нам также нужна идея двух моделей компьютера (машина Тьюринга, действительно): детерминированная и недетерминированная. Детерминированный компьютер - это обычный компьютер, о котором мы всегда думаем; недетерминированный компьютер - это тот, который, как мы привыкли, кроме того, что имеет неограниченный parallelism, так что в любое время, когда вы приходите к ветке, вы создаете новый "процесс" и исследуете обе стороны. Как сказал Йоги Берра, когда вы приходите к развилке на дороге, вы должны ее принять.
Задача решения находится в P, если для получения ответа есть известный алгоритм с полиномиальным временем. Проблема решения в NP, если есть известный алгоритм полиномиального времени для недетерминированной машины, чтобы получить ответ.
Известно, что проблемы, возникающие в P, тривиальны в NP --- недетерминированная машина просто никогда не беспокоит себя, чтобы разветкить другой процесс и действует так же, как детерминированный. Есть проблемы, которые, как известно, не являются ни в P, ни в NP; простой пример - перечислить все битовые векторы длины n. Независимо от того, что принимает 2 n.
(Строго говоря, проблема решения в NP, если недетерминированная машина может прийти к ответу в полином времени, а детерминированная машина может проверить правильность решения в полином времени.)
Но есть некоторые проблемы, которые, как известно, находятся в NP, для которых не известен многорежимный детерминированный алгоритм; другими словами, мы знаем, что они находятся в NP, но не знают, находятся ли они в P. Традиционным примером является проблема решения проблемы Traveling Salesman Problem (решение-TSP): учитывая города и расстояния, есть ли маршрут, который охватывает все города, возвращаясь к начальной точке, меньше, чем на расстоянии? Легко в недетерминированной машине, потому что каждый раз, когда недетерминистский коммивояжер приходит к развилке на дороге, он берет его: клоны направляются в следующий город, который они не посещали, и в конце они сравнивают заметки и видят, любой из клонов занимал меньше х дистанции.
(Затем экспоненциально много клонов начинают бороться, для которых нужно убить.)
Неизвестно, находится ли решение-TSP в P: нет известного многорежимного решения, но нет доказательств, что такого решения не существует.
Теперь еще одно понятие: при решении задач P и Q, если алгоритм может преобразовать решение для P в решение для Q в полиномиальное время, он сказал, что Q является поли-временем, приводимым (или просто приводимым) к P.
Задача NP-полная, если вы можете доказать, что (1) она в NP, и (2) показывают, что ее поли-время сводится к задаче, уже известной как NP-полная. (Трудная часть этого была доказана в качестве первого примера NP-полной проблемы: это было сделано Стив Куком в теореме кулинарии)
Так действительно, что он говорит, что если кто-либо когда-либо найдет многорежимное решение для одной NP-полной проблемы, они автоматически получили один для всех NP-полных проблем; это также означает, что P = NP.
Задача NP-жестка тогда и только тогда, когда она "по крайней мере так же" сложна, как NP-полная проблема. Более обычная проблема с Traveling Salesman для поиска кратчайшего маршрута - NP-hard, а не полностью NP-complete.
Michael Sipser Введение в теорию вычислений это отличная книга, и она очень читаема. Другим большим ресурсом является Скотт Ааронсон Отличные идеи в теоретической компьютерной науке.
Используемый формализм - это рассмотрение проблем решения (проблемы с ответом "Да/Нет", например "этот график имеет гамильтоновский цикл" ) как "языки" - множества строк - входы, для которых ответ Да. Существует формальное представление о том, что такое "компьютер" (машина Тьюринга), и проблема в P, если существует алгоритм полиномиального времени для решения этой проблемы (с учетом входной строки, скажем "Да" или "Нет" ) на машине Тьюринга.
Проблема в NP, если она проверяется в полиномиальное время, т.е. если для входов, где ответ "Да" , существует сертификат (полиномиальный размер), который вы можете проверить, что ответ "Да" в полиномиальное время. [Например. учитывая гамильтоновский цикл в качестве сертификата, вы, очевидно, можете убедиться, что он один.]
Он ничего не говорит о том, как найти этот сертификат. Очевидно, вы можете попробовать "все возможные сертификаты", но это может занять экспоненциальное время; неясно, будете ли вы всегда принимать более чем полиномиальное время, чтобы решить Да или Нет; это вопрос P vs NP.
Задача NP-hard, если возможность решить эту проблему означает возможность решить все проблемы в NP.
Также см. этот вопрос: Что такое NP-полная в информатике?
Но на самом деле все это, вероятно, только смутно для вас; стоит потратить время на чтение, например. Книга сипсеров. Это красивая теория.
Это комментарий к сообщению Чарли.
Задача NP-полная, если вы можете доказать, что (1) она в NP, и (2) показывают, что это поли-время сводится к проблеме, уже известной быть полным NP.
Существует незначительная ошибка со вторым условием. Фактически, вам нужно доказать, что известная NP-полная проблема (скажем Y) является полиномиальным временем, приводимым к этой задаче (назовем ее задачей X).
Обоснование такого способа доказывания состоит в том, что если вы могли бы уменьшить проблему NP-Complete для этой проблемы и каким-то образом решить эту проблему в многопользовательском режиме, вам также удалось найти многорежимное решение для NP-полная проблема, которая была бы замечательной (если не невозможной), с тех пор вам удастся решить давнюю проблему P = NP.
Еще один способ взглянуть на это доказательство - рассмотреть его как использование метода контрацептивного доказательства, в котором, по существу, сказано, что если Y → X, то ~ X → ~ Y. Другими словами, неспособность решить Y в полиномиальное время не представляется возможным, так как это не значит, что нужно решить X в полином времени. С другой стороны, если бы вы могли решить X в многопользовательском режиме, то вы также могли бы решить Y в поли-время. Кроме того, вы могли бы решить все проблемы, которые уменьшают до Y в многопользовательском режиме, а также транзитивность.
Надеюсь, мои объяснения выше достаточно ясны. Хорошим источником является глава 8 "Алгоритм-дизайн" Клейнберга и Тардоса или глава 34 Кормена и др.
К сожалению, лучшие две книги, о которых я знаю (Garey and Johnson и Hopcroft и Ullman) начинаются на уровне градуированной ориентированной математики. Это почти наверняка необходимо, так как весь вопрос очень легко понять или неправильно описать. Jeff чуть не уши уши ушами, когда он попытался подойти к делу в слишком народном/шуточном тоне.
Возможно, лучший способ - просто сделать много практической работы с нотами с большими нотами используя множество примеров и упражнений. См. Также этот ответ. Заметим, однако, что это не совсем то же самое: отдельные алгоритмы могут быть описаны асимптотами, но говорят, что проблема имеет определенную сложность - это утверждение о каждом возможном алгоритме для нее. Вот почему доказательства настолько сложны!
Я помню "вычислительную сложность" от Papadimitriou (надеюсь, что я записал название правильно) в качестве хорошей книги
очень упрощено: проблема NP-hard, если единственный способ ее решить - перечислить все возможные ответы и проверить каждый.
Вот несколько ссылок на эту тему:
В том, что вы знакомы с идеей установленной мощности, то есть количеством элементов в множестве, тогда можно было бы рассмотреть вопрос, например, P, представляющий мощность чисел Integer, в то время как NP является загадкой: это то же самое или он больше, чем мощность всех вещественных чисел?
Моим упрощенным ответом было бы следующее: "Сложность вычислений - это анализ того, насколько сложнее проблема, когда вы добавляете больше элементов".
В этом предложении слово "сложнее" преднамеренно неопределенно, поскольку оно может относиться либо к времени обработки, либо к использованию памяти.
В информатике недостаточно решить проблему. Он должен быть разрешен в разумные сроки. Поэтому, в то время как в чистой математике вы придумываете уравнение, в CS вам нужно уточнить это уравнение, чтобы вы могли решить проблему в разумные сроки.
Это самый простой способ, я могу думать, что это может быть слишком просто для ваших целей.
В зависимости от того, сколько времени у вас есть, может быть, лучше начать с DFA, NDFA, а затем показать, что они эквивалентны. Затем они понимают ND против D и будут понимать регулярные выражения намного лучше, как хороший побочный эффект.