NP-полное сокращение (в теории)

Question

Я хочу внедрить 3 задачи NP-Complete (2 из них известны как NP-Complete, 1 из них - моя собственная идея). Я увидел « этот вопрос » и получил представление о переосмыслении проблем вложения в теории:

• Официант - вор.
• Столы магазинные.
• Продукты - это ценные вещи, имеющие разный вес.
• Вор знает цену и вес всех предметов до ограбления.
• Его целью является наиболее эффективное ограбление (максимальная вместимость использованного рюкзака, наиболее ценные вещи, полученные) с ограблением (получение как минимум 1 предмета) всех магазинов (кратчайший путь к завершению тура по ограблению, также посещение каждого магазина 1 раз).

Эта часть содержит 2 задачи NP-Complete.

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

В настоящее время я не уверен, что моя идея на самом деле является NP-Complete. Может быть, «гравитация» - это не проблема NP-Complete. Но, возможно, именно в этом контексте проблемы коммивояжера и продавца.

Итак, мои вопросы:

1. Замедление замедления NP-вора тоже завершено?

2. Можно ли свести эти три встроенные проблемы к простой NP-полной задаче?

Answer 1

Хорошо, это было просто бит трудно следовать, но я думаю, что я понимаю суть.

Карикатура XKCD показывает вам, как легко сделать реальную задачу NP-полной. (Конечно, поскольку большинство меню имеют небольшое количество товаров и одинаковый набор цен, также легко показать, что есть тривиальный ответ.)

Идея «встраивания» NP-полной задачи, на которую, я думаю, вы ссылаетесь, заключается в нахождении сокращения по времени; Я написал это довольно полностью в другом месте на SO.

Answer 2

Это немного сбивает с толку, но вот мои ответы на некоторые возможные вопросы.

Комбинация двух NP-полных задач будет NP-полной. Фактически, комбинация NP-полной задачи с любой другой проблемой будет NP-полной.

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

Объединенная проблема - это комбинация двух проблем (какие объекты украсть и какой путь выбрать), и она не выглядит для меня более интересной, чем две отдельно, поскольку вы можете решить одну, не беспокоясь о другой , Добавление задержек, зависящих от веса, может соединить проблемы, чтобы они не были независимыми, но вам нужна функция оценки, отличная от того, насколько быстро вы можете совершить оптимальное воровство (оптимальное воровство - это его собственная проблема, а затем это просто модифицированный TSP).

Также вы не сможете брать проблемы, объединять их, усложнять их, а затем делать более простую проблему в целом.

Answer 3

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

Вариант решения этой проблемы по-прежнему NP-завершен, потому что a) мы все еще можем быстро проверить, стоит ли данный тур меньше k, чем в NP, и b) Гамильтонов цикл по-прежнему сводится к нашему TSP с переносом затраты (поскольку мы просто установили все граничные веса равными 1, а все балансовые расходы равны 0 при сокращении).

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

(Решение NP-complete) версии решения задачи о рюкзаке является независимым и может быть последовательно решено с помощью задачи TSP.

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

Answer 4

Спасибо за полезные комментарии, мультфильм дал мне представление о проблемах встраивания. Я немного спешил, когда писал, поэтому я много писал ошибок. Мой основной язык тоже не английский, поэтому редакторы сделали мой вопрос более понятным. Я также хочу еще комментарии для более мозгового штурма.

Чарли Мартин, спасибо за вашу ссылку.

Answer 5

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

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

Подробнее читайте в приличном учебнике или на странице Википедии .