Оценки В-сложности включающего поиска

Теорема 33. Если I = (В^п, V, У) — ЗИП типа Sbool, F ~ базовое множество у допустимое для I, то Т (1,Т) ^ |У|.

Доказательство. Обозначим через 1 набор, состоящий из всех единиц, т. е. 1 = (1,…, 1).

Так как J/(l) = V, то согласно теореме 4.

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

Следствие 13. Если Т — полное базовое множество для типа Sbool) то

ь

Теорема 34. Если I = (В^п, V, >^) — ЗИП типа Sbool > 7* = (F, G) — базовое множество, такое, что К^п С F, то T (I, T) = |V|.

Доказательство. Нижняя оценка следует из теоремы 33, а верхняя оценка достигается на переборном алгоритме, задаваемом ИГ, изображенном на рис. 1.5.

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

Следствие 14. Если Т = (F, G) — базовое множество, такое что /С^п С F, то

ь.

Лемма 31. Если I = (В^п, У, У) — ЗИП типа Sbool• -F = (F, 0) — базовое множество, допустимое для I, где F — одно из трех множеств М^п, /С^п или Х^п, и ИГ U € Ы (1,Т), то T (U) = Q{U).

Доказательство. Так как для любого предиката / 6 F /(1) = = 1, то запрос 1 доходит до всех вершин ИГ U. Напомним, что мы считаем, что ИГ не содержит несущественных ребер. Следовательно, все предикаты соответствующие ребрам ИГ U будут вычислены, т. е. Т (С/, 1) = Q (U). Но так как всегда Т (?/, х) ^ Q (U) для любых (/их, то

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

Из леммы 31 следует, что задача нахождения В-оптимального ИГ для задачи включающего поиска и базового множества переменных сводится к построению оптимальной контактной схемы, реализующей некоторую систему элементарных монотонных конъюнкций.