Если я хочу показать, что проблема является np-сложной, можно ли использовать существующую np-сложную задачу несколько раз? Например, используйте гамильтоновский цикл n раз в графе, где n - количество вершин? Или мне нужно преобразовать граф во что-то, что может быть легко решено существующей np-сложной задачей, используемой 1 раз?
Np-снижение твердости
comment
@PeteKirkham: cstheory предназначена для вопросов исследовательского уровня. Этот вопрос будет закрыт, так как не по теме cstheory.
- person amit schedule 09.01.2012
Ответы (3)
Вам нужно показать прямо противоположное.
Это ничего не доказывает, если вы доказываете, что можете решить свою задачу с помощью задачи NP-Hard. [Вы можете решить любую задачу в NP, используя SAT, с помощью теоремы Кука-Левина].
Вам нужно показать, что если ваша задача разрешима за полиномиальное время, значит, она и NP-сложная. Вот что на самом деле делает сокращение.
Например: если я могу показать, что могу решить кратчайший путь, используя TSP — делает ли кратчайший путь NP-сложным? Конечно нет! Это только показывает, что TSP не менее сложен, чем кратчайший путь!
person
amit
schedule
09.01.2012
Думаю, это ответило на мой вопрос. Я должен преобразовать свою проблему (за полиномиальное время), чтобы ее можно было решить с помощью известной проблемы NP-Hard. Это также означает, что я должен использовать известную задачу NP-Hard только 1 раз, чтобы ответить на мой первоначальный вопрос.
- person Mads Andersen; 09.01.2012
@MadsAndersen: нет. Вам нужно преобразовать NP-сложную задачу в вашу задачу, чтобы показать, что она NP-сложная. или, другими словами: используйте алгоритм для вашей проблемы, чтобы решить NP-сложную задачу. Если это можно сделать за полиномиальное время - ваша задача NP-Hard.
- person amit; 09.01.2012
Путешествие из Парижа в Лондон через Нью-Йорк не доказывает, что этот путь кратчайший.
person
xyz
schedule
09.01.2012
Я не математик, но, конечно, если вы можете доказать, что рассматриваемая проблема по крайней мере так же сложна, как существующая известная NP-сложная задача или их кратные, то это должно быть достаточным доказательством? Здравый смысл подсказывает, что если снять шкуру с леопарда сложнее, чем снять шкуру с двух кошек, то это сложнее, чем снять шкуру с одной кошки, и так далее!
person
Simon Withington
schedule
09.01.2012
Это ерунда. Если я могу найти кратчайшее расстояние между двумя вершинами с помощью TSP, означает ли это, что кратчайший путь является NP-сложным?
- person amit; 09.01.2012
Тогда я оставлю этого леопарда в покое — как я уже сказал, я не математик. Я сказал, что если бы вы могли доказать, что это было «по крайней мере так же сложно», а не «решаемо с помощью», вы уверены, что не немного неправильно меня понимаете?
- person Simon Withington; 09.01.2012
По крайней мере, это не отвечает на вопрос. Вопрос имеет критическую логическую ошибку. каждый ответ, который не упоминает об этом, в основном неверен.
- person amit; 09.01.2012
Этот здравый смысл называется транзитивностью... Что может быть верным для одного отношения и ложным для другого.
- person Lajos Arpad; 09.01.2012
Итак, хотя мое предложение не является неверным, оно неверно из-за ошибки в вопросе? Я думаю, что наши представления о логике совершенно разные;)
- person Simon Withington; 09.01.2012
@TenementFunster: В любом случае я не отрицаю, я просто заявил, что вы не упомянули самую важную часть в правильном ответе на этот вопрос.
- person amit; 09.01.2012
