Почему проблемы NP называются именно так (и NP-hard, и NP-complete)?
Действительно... У меня последний тест на выпускной во вторник, и это одна из вещей, которые я просто никогда не мог понять. Я понимаю, что решение проблемы NP может быть проверено за полиномиальное время. Но при чем тут детерминизм?
И если бы вы могли объяснить мне, где NP-complete и NP-hard получили свои имена, это было бы здорово (я почти уверен, что понимаю их значение, я просто не понимаю, как их имена связаны с тем, что они являются).
Извините, если это тривиально, я просто не могу понять (-:
Спасибо всем!
5 ответов
п
Класс всех проблем, которые могут быть решены детерминированной машиной Тьюринга за полиномиальное время.
NP
Класс всех проблем, которые могут быть решены с помощью недетерминированной машины Тьюринга за полиномиальное время (они также могут быть проверены с помощью детерминированной машины Тьюринга за полиномиальное время.)
NP-Hard
Класс задач, которые "по крайней мере так же сложны, как самые сложные проблемы в NP". Формально, проблема в NP-Hard, если существует NP-полная задача, полиномиальное время которой сводится к Тьюрингу; (также: если это может быть решено за полиномиальное время с помощью машины оракула с оракулом для задачи). Вполне очевидно, откуда взято название.
NPC
Класс задач, которые являются как NP, так и NP-Hard. Что касается именования, даже википедия не уверена, почему она названа так, как она есть.
Начнем с "недетерминированного". Детерминированная машина может находиться в одном состоянии одновременно. Мы действительно можем сделать их. Недетерминированная машина - это теоретическая конструкция, которая может находиться в нескольких состояниях одновременно. (Здесь есть сходство с квантовыми вычислениями, но для наших целей они вводят в заблуждение. Не обращайте на них внимания.)
Если мы хотим решить проблему с помощью детерминированной машины, мы запускаем ее, и она проходит серию шагов, чтобы попытаться найти проблему. Если мы моделируем, используя недетерминированную машину, она может пройти все возможные серии шагов одновременно.
Множество проблем, с которыми мы столкнемся, - это проблемы с решением: с учетом постановки проблемы, есть решение или нет. Найти решение или сообщить, что его нет. Например, предположим, что у вас есть набор логических утверждений: A или не-B, B или C или D, не-D или A или B, .... Учитывая произвольный набор, вы можете найти значения истинности для всех переменных такой, что все утверждения верны?
Теперь давайте рассмотрим P. Предположим, мы представили размер задачи с помощью n. Размером может быть количество городов в задаче коммивояжера, количество логических утверждений в задаче выше, что угодно. При определенном n проблема потребует определенного количества ресурсов для решения в данной системе. Теперь, если мы удвоим ресурсы или вычислительные возможности, что произойдет с размером проблемы, которую мы можем решить? Если задача имеет полиномиальную сложность, что означает в P, размер увеличивается на определенную долю. Это может удвоиться, или подняться на 40%, или на 10%. Напротив, если это имеет экспоненциальную сложность, размер увеличивается на определенное число. Обычно мы думаем о P-задачах как о разрешимых и экспоненциальных задачах так же неразрешимых, как и проблемы, становящиеся большими, хотя это упрощение. С неформальной точки зрения, полиномиальная сложность заключается в том, что она способна последовательно разобраться в проблеме, в то время как экспоненциальная - это рассмотреть все возможные комбинации.
Предположим, что мы можем решить проблему за полиномиальное время на детерминированной машине. Проблема в P. Предположим, что мы можем решить ее за полиномиальное время на недетерминированной машине, что аналогично возможности проверки предложенного решения за полиномиальное время на детерминированной машине. Тогда проблема в NP. Хитрость в том, что мы не можем создавать настоящие недетерминированные машины, поэтому тот факт, что проблема в NP, не означает, что ее практично решить.
Теперь перейдем к NP-завершению. Все проблемы в P находятся в NP. Для задач A и B в NP мы можем сказать, что если A находится в P, то же самое происходит и с B. Это делается путем нахождения способа переформулировать B как проблему A. NP-полная проблема - это такая проблема, что, если она есть в P, каждая проблема в NP находится в P. Как вы можете догадаться, найти способ переформулировать каждую возможную проблему как одну конкретную проблему было нелегко, и я буду просто скажем, что проблема с логическими утверждениями выше (проблема удовлетворенности) была первой доказанной NP-полной. После этого это было проще, так как нужно было только доказать, что если проблема C находится в P, то и Удовлетворенность.
Обычно считается, что есть проблемы, которые есть в NP, но не в P, и недавно было опубликовано доказательство (которое может оказаться, а может и не оказаться действительным). В этом случае программы, завершенные NP, являются самыми сложными проблемами в NP.
Есть проблемы, которые не вписываются в эту форму. Задача коммивояжера, как обычно, состоит в том, чтобы найти самый дешевый маршрут, соединяющий все города. Это не проблема решения, и мы не можем проверить любое предлагаемое решение напрямую. Мы можем сформулировать это как проблему решения: учитывая стоимость C, есть ли маршрут дешевле, чем C? Эта проблема является NP-полной, и, немного поработав, мы сможем решить исходную TSP так же легко, как измененную, NP-полную форму. Следовательно, TSP является NP-сложным, так как это по крайней мере так же сложно, как NP-полная проблема.
NP называется NP (недетерминированное полиномиальное время), потому что проблема NP может быть решена за полиномиальное время с помощью недетерминированной машины Тьюринга.
Начнем с NP: в NP N означает "недетерминированный", а P - "полиномиальное время". Это класс проблем, которые можно решить за полиномиальное время, если у вас есть недетерминированная машина Тьюринга, которая может выполнять ветвление на каждом цикле для параллельного изучения возможностей (альтернативное определение "проверка решения" стало популярным в последнее время, но оно не дает ясности что означает "N"). Недетерминированный компьютер можно сравнить с параллельным компьютером с бесконечным числом процессоров и способностью fork() на каждой инструкции.
Сказать, что проблема Q является "NP-трудной", означает, что любая проблема в NP может быть сведена к проблеме Q (за полиномиальное время). Поскольку отношение "может быть сведено к" между проблемами является отношением порядка, вы можете думать, что "NP-hard" означает "по крайней мере так же сложно, как и все NP-проблемы".
"NP-полная" проблема - это просто одна из проблем в NP, которая является NP-сложной. Я предполагаю, что классу проблем нужно имя, но я не уверен, как объяснить выбор слова "завершить".
Но при чем тут детерминизм?
Из Википедии:
NP - это совокупность всех проблем решения, для которых ответы "да" имеют эффективно проверяемые доказательства того факта, что ответ действительно "да". Точнее, эти доказательства должны быть проверены за полиномиальное время детерминированной машиной Тьюринга
Не уверен насчет истории имен. РЕДАКТИРОВАТЬ: у меня есть предположения, хотя. Далее следует предположение, но я не думаю, что это неразумно.
NP-Hard - это любая проблема, которая, по крайней мере, такая же сложная, как и самая сложная в NP. Следовательно, можно сказать, что рассматриваемая проблема будет иметь NP твердость, следовательно, NP-Hard.
Если какая-либо отдельная проблема в NP-complete может быть решена быстро, то любая проблема в NP также может быть решена быстро. Таким образом, полный набор проблем NP может быть решен.
РЕДАКТИРОВАТЬ 2: Полная статья Википедии (Сложность) указывает:
вычислительная задача является полной для класса сложности, если в формальном смысле это одна из "самых сложных" или "наиболее выразительных" задач в классе сложности