Почему проблемы NP называются так (и NP-hard и NP-complete)?

Ответ 1

P

Класс всех задач, которые можно решить с помощью детерминированной машины Тьюринга в полиномиальное время.

NP

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

NP-Hard

Класс проблем, которые "по крайней мере трудны, чем самые трудные проблемы в NP". Формально проблема заключается в NP-Hard, если есть NP-полная проблема, которая является полиномиальным временем, сводящимся к нему; (также: если он может быть разрешен в полиномиальное время машиной оракула с оракулом для проблемы). Это довольно очевидно, откуда приходит название.

NPC

Класс проблем, как NP, так и NP-Hard. Что касается именования, даже wikipedia не уверен, почему он назван так, как есть.

Ответ 2

Начнем с "недетерминированных". Детерминированная машина может находиться в одном состоянии за раз. Мы можем их создать. Недетерминированная машина - это теоретическая конструкция, которая может быть в нескольких состояниях одновременно. (Здесь есть сходства с квантовыми вычислениями, но для наших целей здесь они вводят в заблуждение. Не обращайте на них внимания.)

Если мы хотим решить проблему с детерминированной машиной, мы запустим ее, и она проведет ряд шагов, чтобы попытаться найти проблему. Если мы моделируем использование недетерминированной машины, она может проходить через все возможные серии шагов одновременно.

Множество проблем, с которыми мы будем иметь дело, - это проблемы с решением: при задании проблемы либо есть решение, либо нет. Найдите решение или сообщите, что его нет. Например, предположим, что у вас есть набор логических операторов: A или not-B, B или C или D, not-D или или B,.... Учитывая произвольный набор, вы можете найти значения истинности для всех переменных так что все утверждения верны?

Теперь рассмотрим P. Предположим, что размер задачи обозначим через n. Размер может быть числом городов в проблеме коммивояжера, количеством логических утверждений в вышеперечисленной проблеме. При определенном n проблема потребует определенного объема ресурсов для решения на данной системе. Теперь, если мы удвоим ресурсы или вычислительные способности, что происходит с размером проблемы, которую мы можем решить? Если проблема связана с полиномиальной сложностью, то есть в P, размер увеличивается на определенную долю. Он может удвоиться или увеличиться на 40%, или на 10%. Напротив, если он имеет экспоненциальную сложность, размер увеличивается на определенное число. Обычно мы рассматриваем проблемы P как разрешимые и экспоненциальные проблемы как неразрешимые, так как проблемы становятся большими, хотя это упрощение. С неформальной точки зрения сложность полинома заключается в том, чтобы разобраться в проблеме последовательно, в то время как экспоненциальная информация должна смотреть на все возможные комбинации.

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

Теперь на NP-complete. Все проблемы в P находятся в NP. Для задач A и B в NP мы могли бы сказать, что если A находится в P, то и B. Это делается путем нахождения способа переформулировать B как проблему типа A. Задача NP-complete такова, что если она находится в P, каждая проблема в NP находится в P. Как вы могли догадаться, найти способ переформулировать все возможные проблемы, поскольку один из них был непростым, и я буду просто скажем, что проблема с логическими высказываниями выше (проблема удовлетворительности) была первой доказанной NP-полной. После этого это было проще, так как нужно было только доказать, что если проблема C была в P, то была и удовлетворительная.

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

Есть проблемы, которые не вписываются в эту форму. Задача Traveling Salesman, как обычно, состоит в том, чтобы найти самый дешевый маршрут, соединяющий все города. Это не проблема решения, и мы не можем проверить какое-либо предлагаемое решение напрямую. Мы можем пересчитать его как проблему решения: учитывая стоимость C, есть ли маршрут, который дешевле, чем C? Эта проблема NP-полная, и с небольшой работой мы можем решить оригинальный TSP так же легко, как и модифицированная форма NP-complete. Поэтому TSP является NP-жестким, поскольку он по крайней мере такой же сложный, как NP-полная проблема.

Ответ 3

NP называется NP (недетерминированным полиномиальным временем), потому что задача NP может быть решена в полиномиальное время недетерминированной машиной turing.

Ответ 4

Начнем с NP: в NP, N для "недетерминированных", а P - для "полиномиального времени". Это класс проблем, которые могут быть решены в полиномиальное время, если у вас есть недетерминированная машина Тьюринга, которая может разветвляться на каждом цикле, чтобы параллельно исследовать возможности (альтернативное определение "проверить решение" стало популярным в последнее время, но оно не делает ясным что означает "N" ). Недетерминированную машину можно сравнить с параллельным компьютером с бесконечным числом процессоров и возможностью fork() для каждой команды.

Говоря о том, что проблема Q является "NP-твердой", означает, что любая задача в NP может быть сведена к задаче Q (в полиномиальное время). Поскольку отношение "можно свести к" между проблемами - это отношение порядка, вы можете думать о "NP-hard" как о значении "по крайней мере так же сложно, как и о всех проблемах NP".

Проблема "NP-complete" - это просто одна из проблем NP, которая NP-hard. Я предполагаю, что классу проблем нужно имя, но я не уверен, как объяснить выбор слова "полный".

Ответ 5

Но что детерминизм имеет к этому отношение?

От Wikipedia:

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

Не уверен в истории имен. EDIT: У меня есть догадки. Далее следует спекуляция, но я не думаю, что это необоснованно.

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

Если какая-либо одна проблема в NP-complete может быть решена быстро, то любая проблема в NP также может быть быстро решена. Таким образом, можно решить полный набор проблем NP.

EDIT2: Википедия Complete (сложность) в статье:

вычислительная проблема завершена для класса сложности, если она в формальном смысле является одной из "самых сложных" или "наиболее выразительных" проблем в классе сложности