Если NP решался в полиномиальное время, может ли быть удовлетворенным решением в полиномиальное время

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

Кроме того, если существует полиномиальность для любого другого NP-Complete problemt, значит ли это, что все остальные NP-Complete могут быть решены за полиномиальное время?

What are the differences between NP, NP-Complete and NP-Hard?

источник

2015-04-28 user10000000

Elaborate, что вы имеете в виду с наоборот. – orlp

Все NP-полные проблемы эквивалентны тем, что если любой из них разрешима в полиномиальное время, все проблемы в NP могут быть решены в полиномиальное время. Тем не менее, этот вопрос действительно вне темы для Stack Overflow. Лучше спросить на http://cs.stackexchange.com/ –

«полное» в NP-полной означает, что если проблема в NP-полной, решение для этой проблемы дает решение любой проблемы в НП с полиномиальной количеством конверсионной обработки.

С точки зрения непрофессионала - если вы решите один NP-полную задачу за полиномиальное время, вы доказали, что NP = P.

источник

2015-04-28 04:32:01 orlp

Да, но если NP решался за полиномиальное время, значит ли это, что все NP-задачи решаются в полиномиальное время. – user10000000

@ user10000000 № – orlp

Нет. Рассмотрим, например, проблему оценки схемы (которая завершена для P). Проблема оценки схемы ставит вопрос: «этот вход удовлетворяет этой логической схеме». Проблема оценки схемы явно находится в NP и содержит полиномиальное решение. Однако это не означает, что SAT схемы имеет решение с полиномиальным временем. Если вы рассматриваете еще одну NP-полную проблему, такую как проблема Гамильтонова пути, и покажите, что эта проблема имеет решение с полиномиальным временем, то Satisfiability также имеет решение polytime. –

Если NP решался в полиномиальное время, может ли быть удовлетворенным решением в полиномиальное время

ответ

Смежные вопросы