singlepost

Есть ли у кого-нибудь данная статья? << На главную или назад  

Помогите с доказательством NP-полноты задачи ОБЩАЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ НАИБОЛЬШЕЙ ДЛИНЫ. В книге Гэри, Джонсона написано, что к ней сводится задача ВЕРШИННОЕ ПОКРЫТИЕ.
Есть ли у кого какая инфа по этому поводу?
И ещё. Никто не знает, где можно достать статью Maier D. (1977) "The complexity of some problems on subsequences and supersequences" J. Assoc. Comput. Mach. 25, 322-336. Там вроде как раз обсуждается решение данной задачи...

7 ответов в теме “Есть ли у кого-нибудь данная статья?”

  1. 1
    Жека Кирпичев ответил:

    Видимо, ты что-то не так понял – наибольшая общая подпоследовательность тривиально находится динамическим программированием за квадратичное время с линейной памятью.

  2. 2
    Овак Мяса ответил:

    не совсем, полностью сформулирую задачу:

    УСЛОВИЕ: Дан конечный алфавит S, конечное множество R слов из S* и положительное целое число K.
    ВОПРОС: Существует ли такое слово w из S*, что |w| >= K и w – подпоследовательность каждого слова для R.

    Действительно если K или |R| фиксированы, то задача решается за полиномиальное время дин. программированием, а если нет?
    Из достоверных источников извсетно что к данной задач сводится Вершинное Покрытие.

  3. 3
    Жека Кирпичев ответил:

    Блин, странно.. Кажется, я видел в книжке "Алгоритмы на строках" забубенное решение этой задачи за линейное (!) время, с помощью суффиксных деревьев.
    Но, видимо, не совсем такой.

    А! Там была задача про наибольшую общую _непрерывную_ подстроку.

  4. 4
    Овак Мяса ответил:

    Возможно, но то что данная задача NP-полная-это точно (см. книгу Гэри, Джонсон "Вычислительные машины и трудноразрешимые задачи" стр. 291 )

  5. 5
    Alexandr Makarov ответил:

    =) Жуков?

  6. 6
    Овак Мяса ответил:

    да )))))

Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.