Изменения

Перейти к: навигация, поиск

Теорема Махэни

1 байт добавлено, 17:58, 5 июня 2012
Нет описания правки
# <tex>\exists i \ne j : z_i=z_j</tex>. Строки <tex>z_i</tex> и <tex>z_j</tex> либо обе лежат в <tex>S</tex>, либо обе не лежат в <tex>S</tex>. Тогда по вышеуказанной причине <tex>x\notin (w_i, w_j]</tex>. Значит мы можем исключить этот полуинтервал из рассматриваемого множества. Таким образом, мы удаляем не менее <tex>\frac 1{r+1}</tex> часть множества подстановок.
# <tex>z_i \ne z_j \, \forall i \ne j</tex>. Как было показано выше, если <tex>x \in [w_0, w_1]</tex>, то все <tex>z_i</tex>, начиная с <tex>z_1</tex> , лежат в <tex>S</tex>, но тогда <tex>S</tex> содержит <tex>r+1</tex> строку длины не более, чем <tex>q(|\phi|)</tex>, что противоречит условию <tex>|\{x\in S\, |\, |x| \le q(|\phi|)\}| \le r(|\phi|)</tex>. Следовательно, <tex>x\notin[w_0,w_1]</tex>, то есть его можно убрать из рассмотрения.
В обоих случаях мы сузили область поиска как минимум на <tex>\frac 1{r+1}</tex> её размера.
Анонимный участник

Навигация