Нахождение ближайшей подстроки: различия между версиями

Теорема 4 также позволяет по-новому взглянуть на вопрос аппроксимируемости задачи: в схеме PTAS для задачи CLOSEST SUBSTRING показатель степени полинома, ограничивающего время выполнения, зависит от коэффициента аппроксимации. Эта схема не является «эффективной» PTAS (EPTAS), то есть PTAS с временем выполнения <math>f(\epsilon) \cdot n^c</math> для некоторой функции f и некоторой константы c и, следовательно, вряд ли окажется полезной на практике. Из теоремы 4 следует, что PTAS с временем выполнения <math>n^{(O(1 / \epsilon^4)}</math>, представленная в [6], скорее всего,не может быть улучшена до EPTAS. Точнее говоря, не существует PTAS с временем выполнения <math>f(\epsilon) \cdot n^{o(log \; 1 \ \epsilon)}</math> для задачи CLOSEST SUBSTRING, за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время. Кроме того, из доказательства теоремы 4 также следует

Теорема 5 [7]. Не существует алгоритма, решающего задачу CLOSEST SUBSTRING приближенно за время f(d; k) ■ no(logd) и точно за время g(d; k) • no(logl°gk) для некоторых функций f и g, за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время.

Для неограниченных алфавитов были получены более строгие границы за счет того, что было показано, что не существует PTAS с временем выполнения /(e) • и°'1/е' для задачи CLOSEST SUBSTRING для любой функции f, за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время. Следующие утверждения дают возможность получить точные алгоритмы решения задачи CLOSEST SUBSTRING для небольших фиксированных значений d и k, соответствующие границе, приведенной в теореме Theorem 5:

Теорема 6 [7]. Задача CLOSEST SUBSTRING может быть решена за время f(d) ■ n°^°&^ для некоторой функции f, где, более точно, f(d) = \E.

Теорема 7 [7]. Задача CLOSEST SUBSTRING может быть решена за время g(d; k) ■ nO(loglogk) для некоторой функции g, где, более точно, g(d; k) = (\E\d)0(kd\.

Относительно заданного в задаче параметра L задачу CLOSEST SUBSTRING можно тривиально решить за время O(j^l1" • n), проверяя все возможные строки над алфавитом S.