T>>NP-полная = эквивалентна классу NP-полных задач (т.е. сводима к одной из них) T>>NP-трудная = стопудово полиномиально неразрешима
A>Ну вот я и говорю, что она NP-трудна. А вот NP-полноты в ней на первый взгяд действительно не видно.
Здравствуйте, alebab, Вы писали:
T>>NP-полная = эквивалентна классу NP-полных задач (т.е. сводима к одной из них) T>>NP-трудная = стопудово полиномиально неразрешима
A>Ваши рассуждения немного противоречивы. Согласен с определением NP-полноты, кроме того, что записано в скобках.
A>Любую полиномиально разрешимую задачу можно свести к любой NP-полной. однако полиномиально разрешимые задачи не становятся изза этого NP-полными.
В данном контексте под сводимостью подразумевается равносильность.
A>Ровно поэтому я и не утверждаю, что задача о "суммарной строке" NP-полна. А всего лишь говорю, что она NP-трудна
Здравствуйте, Tan4ik, Вы писали:
T>Здравствуйте, alebab, Вы писали:
A>>Поясните пожалуйста
T>NP-полная = эквивалентна классу NP-полных задач (т.е. сводима к одной из них) T>NP-трудная = стопудово полиномиально неразрешима
Как всё запущено...
Задача распознавания называется NP-полной, если к ней полиномиально сводится любая NP-полная задача. (например, задача о покрытии, выполнимости и т.д., изначально перечень первых 6 NP-полных задач был дан Куком).
Оптимизационная задача называется NP-трудной, если к ней полиномиально сводится какая-нибудь NP-полная задача распознавания.
Таким образом, решив оптимизационную NP-трудную задачу мы автоматически получаем полиномиальный алгоритм для всех NP-полных задач.
Здравствуйте, LCR, Вы писали:
A>>>Поясните пожалуйста
T>>NP-полная = эквивалентна классу NP-полных задач (т.е. сводима к одной из них) T>>NP-трудная = стопудово полиномиально неразрешима
LCR>Как всё запущено...
LCR>Задача распознавания называется NP-полной, если к ней полиномиально сводится любая NP-полная задача. (например, задача о покрытии, выполнимости и т.д., изначально перечень первых 6 NP-полных задач был дан Куком).
LCR>Оптимизационная задача называется NP-трудной, если к ней полиномиально сводится какая-нибудь NP-полная задача распознавания.
LCR>Таким образом, решив оптимизационную NP-трудную задачу мы автоматически получаем полиномиальный алгоритм для всех NP-полных задач.
Хм...
Я в шоке. Мой мир рушится. Я отчетливо помню, что не раз читал то определение, что поведал. Там еще приводился пример NP-трудной задачи: "Напечатать все перестановки 1..N". С объяснением, что "очевидно, что мы точно не сможем это сделать за полиномиальное время". Теперь я знаю чем займусь вечером. Буду перечитывать Кнута, Кормана и т.п. на предмет определения NP-тружных задач.
Здравствуйте, Tan4ik, Вы писали:
T>Я в шоке. Мой мир рушится. Я отчетливо помню, что не раз читал то определение, что поведал. Там еще приводился пример NP-трудной задачи: "Напечатать все перестановки 1..N". С объяснением, что "очевидно, что мы точно не сможем это сделать за полиномиальное время". Теперь я знаю чем займусь вечером. Буду перечитывать Кнута, Кормана и т.п. на предмет определения NP-тружных задач.
Одно дело, когда в самом задании сказано выполнить что-то K раз, где K > O(N^p).
"Вывести все числа от 1 до 2^2^N" — ещё более круто, чем факториал.
А совсем другое — сделать что-то, что полным перебором решается за T > O(N^p).
Например, найти i-ю перестановку.
версию решиния убрал — щас заряжу как задачку. — К
Здравствуйте, Tan4ik, Вы писали:
T>Хм... T>Я в шоке. Мой мир рушится. Я отчетливо помню, что не раз читал то определение, что поведал. Там еще приводился пример NP-трудной задачи: "Напечатать все перестановки 1..N". С объяснением, что "очевидно, что мы точно не сможем это сделать за полиномиальное время". Теперь я знаю чем займусь вечером. Буду перечитывать Кнута, Кормана и т.п. на предмет определения NP-тружных задач.
Молодец!
Про перечисление перестановок...
Напечатать все перестановки — это переборная задача, но это не задача распознавания (следовательно она не может лежать в NP по определению). Также к ней не сводится полиномиально ни одна задача из NP.
Можно выдумать задачу из NP (даже из P), которая бы экспоненциально сводилась к перечислению перестановок.
Естественно, есть другие задачи (точно не в NP), которые сводились бы к перечислению перестановок полиномиально.
Но одновременно невозможно.
То есть, задача перечисления перестановок не NP-трудна. Она просто не удовлетворяет определению! Тебя гнусным образом дезинформировали!
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Перекуём баги на фичи!
