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

'''Теорема 2 [6]. Задача CLOSEST SUBSTRING (также как CLOSEST STRING) допускает применение аппроксимационных схем с полиномиальным временем выполнения (PTAS), в которых целевой функцией является минимальное расстояние Хэмминга d.'''

'''Теорема 3 [3]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра k даже для бинарного алфавита.'''

'''Теорема 4 [7]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра d даже для бинарного алфавита.'''

Теорема 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 за время <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-КНФ может быть решена за субэкспоненциальное время [10]. Следующие утверждения дают возможность получить точные алгоритмы решения задачи CLOSEST SUBSTRING для небольших фиксированных значений d и k, соответствующие границе, приведенной в теореме 5:

Относительно заданного в задаче параметра L задачу CLOSEST SUBSTRING можно тривиально решить за время <math>O(|\Sigma|^L \cdot n)</math>, проверяя все возможные строки над алфавитом <math>\Sigma</math>.

Остается нерешенным вопрос [7], можно ли аппроксимационную схему с временем выполнения <math>n^{O(1 / \epsilon^4)}</math>, предложенную в работе [6], улучшить до <math>n^{O(log \; 1 / \epsilon)}</math> в соответствии с границей, полученной на основе теоремы 4.