Если я хочу показать, что проблема в np-hard, нормально ли использовать существующую проблему np-hard несколько раз? Например, используйте гамильтоновский цикл n раз в графе, где n - число вершин? Или мне нужно преобразовать граф во что-то, что можно легко решить с помощью существующей np-hard проблемы, используемой 1 раз?Np-hardness reduction
Вам нужно показать точный oposite.
Это не доказывает ничего, если вы докажете, что можете решить свою проблему с проблемой NP-Hard. [Вы можете решить каждую проблему в NP, используя SAT, по Cook-Levin Theorem].
Вам нужно показать, что если ваша проблема разрешима в полиномиальное время, это проблема NP-Hard. Это то, что на самом деле делает сокращение.
Например: Если могу показывать, я могу решить shortest path, используя TSP - делает ли он кратчайший путь NP-Hard? Конечно нет! Это только показывает, что TSP по крайней мере такой же сложный, как и самый короткий путь!
Я думаю, это ответ на мой вопрос. Я должен преобразовать свою проблему (в полиномиальное время), чтобы она могла решить известную проблему NP-Hard. Это также означает, что я должен использовать только известную проблему NP-Hard 1 раз, чтобы ответить на мой первоначальный вопрос. –
@MadsAndersen: no. Вам нужно ** преобразовать NP-Hard проблему в вашу проблему **, чтобы показать, что это NP-Hard. или другими словами: Используйте алгоритм для решения проблемы NP-Hard. Если это можно сделать в полиномиальное время - ваша проблема NP-Hard. – amit
Спасибо большое - помог мне! –
Я не математик, но, конечно, если вы можете доказать, что проблема, о которой идет речь, по крайней мере такая же сложная, как и существующая проблема с неизвестными NP-трудностями или ее кратность, чем это должно быть достаточно доказательство? Здравый смысл предполагает, что если скининг леопарда более сложный, чем скинирование двух кошек, то это более сложное, чем скинирование одной кошки и т. Д.!
Это неудобство. Если я могу решить кратчайшее расстояние между двумя вершинами, используя TSP, значит, самый короткий путь - NP-Hard? – amit
Я оставлю этого леопарда в одиночестве, тогда как я сказал, что я не математик. Я действительно сказал, что если бы вы могли доказать, что это было «по крайней мере сложным», а не «разрешимым», вы уверены, что не ошибаетесь меня немного? –
По крайней мере, он не отвечает на вопрос. Вопрос имеет критический логический сбой. каждый ответ, который не упоминает об этом, в основном неправильный. – amit
Путешествие из Парижа в Лондон через Нью-Йорк не доказывает, что этот путь является самым коротким.
@PeteKirkham: cstheory для вопросов уровня исследования. Этот вопрос будет закрыт, так как это не по теме для cstheory. – amit