Помогите с доказательством NP-полноты задачи ОБЩАЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ НАИБОЛЬШЕЙ ДЛИНЫ. В книге Гэри, Джонсона написано, что к ней сводится задача ВЕРШИННОЕ ПОКРЫТИЕ.
Есть ли у кого какая инфа по этому поводу?
И ещё. Никто не знает, где можно достать статью Maier D. (1977) "The complexity of some problems on subsequences and supersequences" J. Assoc. Comput. Mach. 25, 322-336. Там вроде как раз обсуждается решение данной задачи…
1 февраля 2008 в 16:04
да )))))
1 февраля 2008 в 16:01
=) Жуков?
1 февраля 2008 в 1:00
Блин, странно.. Кажется, я видел в книжке "Алгоритмы на строках" забубенное решение этой задачи за линейное (!) время, с помощью суффиксных деревьев.
Но, видимо, не совсем такой.
А! Там была задача про наибольшую общую _непрерывную_ подстроку.
1 февраля 2008 в 1:00
Возможно, но то что данная задача NP-полная-это точно (см. книгу Гэри, Джонсон "Вычислительные машины и трудноразрешимые задачи" стр. 291 )
1 февраля 2008 в 0:02
не совсем, полностью сформулирую задачу:
УСЛОВИЕ: Дан конечный алфавит S, конечное множество R слов из S* и положительное целое число K.
ВОПРОС: Существует ли такое слово w из S*, что |w| >= K и w – подпоследовательность каждого слова для R.
Действительно если K или |R| фиксированы, то задача решается за полиномиальное время дин. программированием, а если нет?
Из достоверных источников извсетно что к данной задач сводится Вершинное Покрытие.
31 января 2008 в 23:01
Видимо, ты что-то не так понял – наибольшая общая подпоследовательность тривиально находится динамическим программированием за квадратичное время с линейной памятью.