Не детерминированные полиномиальные решения всегда нежелательны в отношении детерминированных полиномиальных решений, верно ли это? Просьба дать соответствующие аргументы.Недетерминированные полиномиальные решения по детерминированному полиномиальному решению
Каждый детерминированным полиномиальное решение может быть переведен на недетерминистическую полиномиальной [поскольку P является подмножеством NP]
Мы не знаем, если на противоположном верно или нет [мы не знаем, если Р = NP или P! = NP], поэтому, если P! = NP, возникают проблемы [все проблемы NP-Complete], которые имеют не детерминированные полиномиальные решения, но не полиномиальные решения.
Таким образом, так как мы можем преобразовать детерминированное полиномиальное решение недетерминированного полиномиальным решения, но мы не знаем, что мы можем сделать на противоположном - если мы имеем детерминированное полиномиальное решение - мы actuall имеем также недетерминированные один.
Недетерминированный и NP (не многочлены) - совсем другие вещи. – ElKamina
@ElKamina: NP означает Недетерминированный многочлен, а не не многочлен. Самый короткий путь для instacne - проблема P и NP. [TSP] (http://en.wikipedia.org/wiki/Travelling_salesman_problem), однако, находится в NP, но только в P, если P = NP. Я рекомендую вам прочитать страницу [wikipedia для NP] (http: //en.wikipedia.org/wiki/NP_% 28complexity% 29), который начинается с: «Аббревиатура аббревиатуры NP относится к« недетерминированному полиномиальному времени ». – amit
Спасибо за информацию! – ElKamina
В дополнение к информативному ответу Амита, иногда - для практических входов - решения NP могут быть лучше. Например, рассмотрим экспоненциальный алгоритм для NP-задачи, который имеет T (n) = 2^n. Рассмотрим проблему, наилучшая временная сложность которой, по-видимому, T (n) = (1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 , 000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 , 000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 , 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,009) п^2. Это многочлен, но я бы скорее решил проблему экспоненциальности.
Если вопрос заключается в том, следует ли использовать для решения одной и той же проблемы решение, основанное на экспоненциальном или худшем случае, или полиномиальное решение, как правило, это ответ: он зависит от вашего размера ввода. Алгоритмы с более высокими асимптотическими сложностями могут быть быстрее для большинства входов разумного размера; хотя будет смысл использовать алгоритм с более низкой степенью сложности, эта точка никогда не может быть достигнута на практике (или в жизни Вселенной).
EDIT: Он также может зависеть от других характеристик входа. Например, quicksort может опередить mergesort, хотя mergesort доказуемо лучше, чем quicksort в худшем случае. Если вы знаете, что очень маловероятно, чтобы ваши данные были в такой форме, что в худшем случае для быстрой сортировки, быстрой сортировки, возможно, стоит попробовать.
Это вопрос домашнего задания? – CountMurphy
Это вопрос домашней работы? Пожалуйста, предоставьте более подробную информацию. – ElKamina
Я понимаю, что это было закрыто, я не думаю, что какой-либо из ответов отвечает на то, что он спрашивает. Вопрос лучше сформулирован: «Является ли алгоритм P более предпочтительным, чем алгоритм, который находится в NP, но не в P (a.k.a. NP-P)?» В качестве ответа я бы сказал, что это зависит от ситуации. Случай и точка, в криптографии, вы почти всегда предпочитаете алгоритм NP для решения вашего кода, чем P. В общем, когда цель действительно решает проблему, а не препятствует ее решению, решение P лучше, чем решение NP, которое не находится в P., это предполагает, что мы не знаем, если P = NP –