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

'''Теорема 1. Существует схема аппроксимации с полиномиальным временем выполнения для задачи поиска ближайшей строки.'''

'''Теорема 2. Существует схема аппроксимации с полиномиальным временем выполнения для задачи поиска ближайшей подстроки.'''

'''Теорема 3. Существует схема аппроксимации с полиномиальным временем выполнения для задачи выбора различающей подстроки. А именно, для любого константного значения <math>\epsilon > 0</math> алгоритм находит строку s длины L, такую, что для каждого <math>s_i \in B</math> существует имеющая длину L подстрока <math>t_i</math> строки <math>s_i</math> с <math>d(t_i, s) \le (1 + \epsilon)d_b</math> и для каждой подстроки <math>u_i</math> длины L каждой строки <math>g_i \in G</math> имеет место <math>d(u_i, s) \ge (1 - \epsilon) d_g</math>, если существует решение для исходной пары <math>(d_b \le d_g)</math>. Поскольку существует полиномиальное количество таких пар <math>(d_b, d_g)</math>, мы можем за полиномиальное время перебрать все возможности и найти наиболее подходящую аппроксимацию для соответствующей конкретной задачи.'''