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

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

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