4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 36: | Строка 36: | ||
'''Теорема 3[3]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра k даже для бинарного алфавита.''' | '''Теорема 3 [3]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра k даже для бинарного алфавита.''' | ||
'''Теорема 4[7]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра d даже для бинарного алфавита.''' | '''Теорема 4 [7]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра d даже для бинарного алфавита.''' | ||
Строка 45: | Строка 45: | ||
Теорема 4 также позволяет по-новому взглянуть на вопрос аппроксимируемости задачи: в схеме PTAS для задачи CLOSEST SUBSTRING показатель степени полинома, ограничивающего время выполнения, зависит от коэффициента аппроксимации. Эта схема не является «эффективной» PTAS (EPTAS), то есть PTAS с временем выполнения <math>f(\epsilon) \cdot n^c</math> для некоторой функции f и некоторой константы c и, следовательно, вряд ли окажется полезной на практике. Из теоремы 4 следует, что PTAS с временем выполнения <math>n^{ | Теорема 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]. Не существует | '''Теорема 5 [7]. Не существует точных алгоритмов решения задачи CLOSEST SUBSTRING за время <math>f(d, k) \cdot n^{o(log \; d)}</math> и <math>g(d, k) \cdot n^{o(log \; log \; k)}</math> для некоторых функций f и g, за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время.''' | ||
Для неограниченных алфавитов были получены более строгие границы за счет того, что было показано, что не существует PTAS с временем выполнения <math>f(\epsilon) \cdot n^{o(1 / \epsilon)}</math> для задачи CLOSEST SUBSTRING для любой функции f, за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время. Следующие утверждения дают возможность получить точные алгоритмы решения задачи CLOSEST SUBSTRING для небольших фиксированных значений d и k, соответствующие границе, приведенной в теореме 5: | Для неограниченных алфавитов были получены более строгие границы за счет того, что было показано, что не существует PTAS с временем выполнения <math>f(\epsilon) \cdot n^{o(1 / \epsilon)}</math> для задачи CLOSEST SUBSTRING для любой функции f, за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время [10]. Следующие утверждения дают возможность получить точные алгоритмы решения задачи CLOSEST SUBSTRING для небольших фиксированных значений d и k, соответствующие границе, приведенной в теореме 5: | ||
Строка 59: | Строка 59: | ||
'''Теорема 7 [7]. Задача CLOSEST SUBSTRING может быть решена за время <math>g(d, k) \cdot n^{O(log \; log \; k)}</math> для некоторой функции g, где, более точно, <math>g(d, k) = (|\Sigma| d)^{O(kd)}</math>.''' | '''Теорема 7 [7]. Задача CLOSEST SUBSTRING может быть решена за время <math>g(d, k) \cdot n^{O(log \; log \; k)}</math> для некоторой функции g, где, более точно, <math>g(d, k) = (|\Sigma| d)^{O(kd)}</math>.''' | ||
Относительно заданного в задаче параметра L задачу CLOSEST SUBSTRING можно тривиально решить за время <math>O(|\Sigma|^L \cdot n)</math>, проверяя все возможные строки над алфавитом | Относительно заданного в задаче параметра L задачу CLOSEST SUBSTRING можно тривиально решить за время <math>O(|\Sigma|^L \cdot n)</math>, проверяя все возможные строки над алфавитом <math>\Sigma</math>. | ||
== Применение == | == Применение == |
правка