Проблемы с НП и нужна какая-то деталь?

Я вижу один решенный на Алгоритмы. Что из следующего есть в NP?

a) Decision Version of TSP 

b) Array is Sorted?

c) Finding the maximum flow network

d) Decision version of 0/1 knapsack?

Моя заметка, говорит, что все это в NP, любой может добавить немного деталей для каждого, почему? а меня смущает около 0/1 ранца, это NP? NP-трудной? или NP-Complete?

Благодарю.

Источник

2 ответа

Они все в НП, потому что:

  1. Это проверяется за полиномиальное время. Учитывая некоторый маршрут, мы можем легко проверить, не превышает ли его длина данное значение.

  2. Это в классе P (я думаю, что решение за полиномиальное время очевидно), что автоматически означает, что это в NP.

  3. Опять же, существует решение за полиномиальное время, что означает, что оно находится в P. Таким образом, оно находится в NP.

  4. Мы можем проверить это за полиномиальное время, учитывая соответствующее подмножество. Следовательно, это в NP по определению.

О версии решения задачи о рюкзаке 0/1: в NP. Он также известен как NP-полный (доказательство слишком длинное, чтобы писать здесь, вот ссылка: доказательство). Это также означает, что это NP-сложная задача (любая NP-полная задача является NP-сложной по определению).

PS Я предполагаю, что "найти максимальный поток" означает версию решения здесь.

Источник

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

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

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

Теперь первая проблема явно в NP. Можно недетерминированным образом сгенерировать все возможные циклы длиной n-1 или менее и позволить верификатору проверить, все ли города посещены ровно один раз, а общий вес меньше или равен заданной длине.

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

Третий также может быть сделан детерминистически: есть алгоритм Max-Flow, который работает в O (V ^ 2 E).

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

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

  1. Решение проблемы коммивояжера; а также
  2. Решение задачи о ранце

С научной точки зрения, P и NP содержат только варианты решения проблем. Чтобы обойти эту проблему, они ввели FP и FNP. Здесь мы будем предполагать, что FP "немного равен" P (из контекста ясно, является ли это вариантом решения), а FNP более или менее эквивалентен, но, очевидно, недостаточно, чтобы люди, читающие предыдущие комментарии, могли понять с равенством мы имеем в виду "эквивалентность" NP. Большинство разработчиков алгоритмов (даже академических) тоже не делают различий и говорят, что их "алгоритм находится в P" (тогда как они фактически означают, что их алгоритм находится в FP). Можно сказать, что это "экономический взгляд" (в отличие от "академического взгляда").

Итак, подведем итог: таблица гласит:

Problem                             | P | NP | NP-hard | NP-complete
------------------------------------+---+----+---------+------------
a) Decision Version of TSP          | * | Y  | Y       | Y
b) Array is Sorted?                 | Y | Y  | ?       | ?
c) Finding the maximum flow network | Y | Y  | ?       | ?
d) Decision version of 0/1 knapsack | * | Y  | Y       | Y
------------------------------------+---+----+---------+-------------

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

Так что в случае P=NP, вопросительные знаки (?) должно быть Yиначе они должны быть N, * наоборот: в случае P=NP ответ Yв случае P! = NP (очень вероятно), * является N,

Источник
Другие вопросы по тегам