Леммы о сведении

В данном разделе мы приведем два случая, когда нижние оценки сложности для одних задач могут быть использованы для оценки сложности других задач.

Лемма 10 (первая лемма о сведении). Если I = (X, V, р) —.

ЗИП₇ F = (F, 0) — измеримое базовое множество, допустимое для I, то для любой такой ЗИП Г = (X, V', p), что ЩГ, Т) ф 0 u V С V', выполняется T (IF) ^ Т (1,Т) и Т (/^/, Т) ^ Т (/, Т).

Доказательство. Возьмем произвольный ИГ U 6 Ы{Г, Т). Уберем нагрузку с листьев, которым соответствуют записи из V' V, и объявим эти листья обычными вершинами. Если после этого образовались несущественные ребра и вершины, то уберем их. Получившийся ИГ обозначим через U'. Понятно, что U' разрешает ЗИП I и T (U') ^ T (U) и T (U') ^ T (U). Таким образом, мы показали, что для любого ИГ U 6 и (Г, Т) существует такой ИГ U' 6 U (I, Т), что T (U') ^ T (U) и Г (?/') ^ T (U). Откуда следует, что Т (Г, Т) > Т (1,Т) и Т{Г, Т)>Т{1,Т).

Тем самым лемма доказана.

Лемма 11 (вторая лемма о сведении). Пусть I = (X, V, p) 6 6 5 = (Х, У, р, Р,<�т) и Г = (X, V', p') 6 5' = (Х, У, р', Р,<�т) — такие ЗИП, что |V| = У и существует взаимно однозначное соответствие ф: V —> V, такое, что для любой записи у 6 V⁷ выполухяется 0{ф{у), р') С 0(у, р); F = {F, 0) — измеримое базовое множество, допустимое для I и V, такое, что для любой записи у 6 У имеем Х_У,_Р € F, тогда Т (Г, Т) > T (I, T) ti T (/', F) ^ f (/, F).

Доказательство. Возьмем произвольный ИГ U 6 U (JT). Для произвольного листа, а ИГ U заменим его нагрузку у на ф (у), а нагрузку всех ребер, входящих в лист а, заменим на Хф (у), р? В результате мы получим ИГ U который разрешает ЗИП I и T (U') ^ T (U) и T (U') ^ ^ T (U). Откуда легко получается утверждение леммы.

Тем самым лемма доказана.

Как следствие первой леммы о сведении мы легко можем получить нижнюю оценку сложности для класса задач, у которых в ответе всегда не более чем п записей.

Теорема 10. Если п — натуральное число, I = (X, V, p) — ЗИП, обладающая В_п -свойством, Т = (F, G) — измеримое базовое множество, допустимое для I, то Т (1,Т) ^ W ([|V|/n]), и если кроме того ЗИП I, такая, что для любой записи у? V выполняется Р(0(у, р)) = = r, mo T (lF)*r-R ([V/n]).

Доказательство. Выделим в библиотеке V подмножество V', которое обладает В-свойством. Это можно сделать следующим образом. Возьмем произвольную такую запись у, что ее тень пересекается с тенью хотя бы одной другой записи из V. Выбросим из V все записи, отличные от у, чьи тени пересекаются с тенью записи у. При этом число выброшенных записей будет не более чем n —1. С получившейся библиотекой данную операцию будем повторять до тех пор пока это возможно. В результате получим библиотеку V', обладающую В- свойством, причем V' ^ [|V|/n].

Теперь, применив к ЗИП Г = (X, Vр) теоремы 7 и 8 и первую лемму о сведении, получим требуемое.

Тем самым теорема доказана.

Второй леммой о сведении удобно пользоваться, когда пересечения между тенями записей есть, но они малы по сравнению с самими тенями. Тогда можно перейти к такому отношению поиска, которое «подрезает» тени так, чтобы они взаимно не пересекались.

Другой случай использования второй леммы о сведении — это когда тени записей имеют примерно одинаковые, но все же разные вероятности, что можно сформулировать в виде теоремы.

Теорема 11. Если I = (X, V, p)? S = (Х, У, р, Р,<�т) — ЗИП, обладающая Всвойством, такая, что для любой записи у G V выполняется Р(0(у, р)) ^ г и существует такое множество А_у € G а, что А_у С 0(у, р) и Р (Л_У) = г; Т = (F, G) — измеримое базовое множество, допустимое для I, такое, что для любой записи у 6 V имеем /a_v G F, где Nf_Av = А_у, то Т (1,Т) ^ г • R (V).

Доказательство. Рассмотрим отношение поиска р такое, что 0(у, р') = А_у для любой записи у € V, и ЗИП V — (X, V, p'). Теперь воспользовавшись теоремой 7 и второй леммой о сведении, получаем ЩГ) (!,?)>*• mV).

Тем самым теорема доказана.