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

'''Теорема 3. Существует схема аппроксимации с полиномиальным временем выполнения для задачи выбора различающей подстроки. А именно, для любого константного значения <math>\epsilon > 0</math> алгоритм находит строку длины 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, d(u_i, s) \ge (1 — \epsilon) d_g</math>, если существует решение для исходной пары <math>(d_b \le d_g)</math>. Поскольку существует полиномиальное количество таких пар <math>(d_b, d_g)</math>, мы можем за полиномиальное время перебрать все возможности и найти наиболее подходящую аппроксимацию для соответствующей конкретной задачи.'''