Снижение твердости нп

Question

Если я хочу показать, что проблема np-hard, можно ли использовать существующую проблему np-hard несколько раз? Например, используйте гамильтонов цикл в графе n раз, где n - число вершин? Или мне нужно преобразовать график во что-то, что может быть легко решено существующей проблемой np-hard, использованной 1 раз?

Answer 1

Вам нужно показать точный опозит.

Это ничего не доказывает, если вы докажете, что можете решить свою проблему с проблемой NP-Hard. [Вы можете решить любую проблему в NP, используя SAT, по Теорема Кука-Левина ].

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

Например: если я могу показать, что могу решить кратчайший путь , используя TSP - делает ли он кратчайший путь NP-Hard? Конечно, нет! Это только показывает, что TSP по крайней мере так же тверд, как кратчайший путь!

Answer 2

путешествие из Парижа в Лондон через Нью-Йорк не доказывает, что этот путь самый короткий.

Answer 3

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