Нижняя оценка сложности включающего поиска для базового множества переменных в классе бесновторных или древовидных

ИГ. Нижняя оценка включающего поиска, приведенная в теореме 26, в два раза лучше мощностной нижней оценки. В случае, когда базовое множество состоит из множества переменных Х^п, удается найти такие задачи, для которых была получена нижняя оценка, большая по порядку, чем мощностная нижняя оценка. К сожалению, доказательство этого факта проходит только в предположении древовидности графа. Так как в общем случае согласно теореме 22 оптимальные графы не древовидны, то это сужает область действия этого результата на класс бесповторных (поскольку для них доказана древовидность оптимальных графов) или древовидных ПИГ. Но возможно результат верен и в классе ПИГ, поскольку для найденных задач не доказана недревовидность оптимального графа. Результат данного раздела опубликован в [35, 159].

Теорема 28. Если базовое множество имеет вид Т — (Х^п, 0) и к (п), т (п) и а (п) такие числа, зависящие от п, что

при п —" оо, то для любого такого к (п) существуют такие ЗИП ь.

Ik = (В^п, V*, У) типа Sbooi, У которых |V*| = к, что для них при п -> —> оо справедливо соотношение

где Ud{Ik, T) — множество всех ИГ над базовым множеством Т, разрешающих ЗИП Ik и являющихся бесповторными или древовидными.

Доказательство. Пусть р (п) — такое, что р^т ^ к > (р — 1)^ш. Оценим величину р/п. Для этого рассмотрим два случая: когда т = = const, и т —> оо при п -4 оо.

В первом случае получим.

поскольку, как легко видеть, а (гг) = б (п).

Во втором случае, используя формулу Стирлинга (см., например, (13, с. 282]), можем получить аналогичный результат.

Пусть г (п) такое, что.

Договоримся обозначать запись у Е В^п через ее характеристическую функцию, т. е. представлять ее в виде конъюнкции переменных, номера которых совпадают с номерами разрядов вектора у, в которых стоят 1.

Разобьем все множество переменных Х^п на т + г + 1 взаимно непересекающисся части так, что в первых т частях находится по р переменных, в (т 4- г)-й части (г = 1, г) находится рт* переменных, а в (т + г + 1)-й части все оставшиеся переменные. В соответствии с неравенством (3.3) такое разбиение возможно. Переменные из г-й части Х^п (г = l, ra + r + 1) будем обозначать через х*, т. е. верхний индекс переменной будет говорить о том, какой части принадлежит переменная.

Рассмотрим библиотеку.

Поскольку каждая запись … *3^*7|⁺¹… полностью определяется набором (gi,…, g_m), то мощность библиотеки V равна V = = р^т ^ к. Отметим также, что для любого j € {1, г}

Покажем, что любая пара различных векторов из V имеет не более чем т-1 одинаковую переменную. Возьмем произвольную пару векторов из V:

Пусть qi_t ф q_|# ц € {l, m}, l = l, s, и qj = (f- при условии, что j € {l, m} {i/: l = l, s}. Так как векторы различные, то s > 0.

Пусть fj, = f'_jt, jl e {ТГг}, г = М, и fj Ф /' при условии, что j € {l, r} {ji: I = 1, t}. Покажем, что t < s.

Предположим, что это не так, т. е. t ^ s.

Рассмотрим систему уравнений.

Взяв в этой системе первые s уравнений, получим.

Определитель этой системы.

есть минор определителя Вандермонда и не равен 0, поскольку — положительные числа. Это довольно простой факт и встречается в качестве упражнения, например, в [85, с. 54]. Поэтому эта система имеет единственное решение.

Но согласно предположению.

Противоречие. Значит, t < s и, следовательно, любая пара записей из.

V имеет не более чем т — 1 общую переменную.

Рассмотрим такую библиотеку V что К' С V и |V'| = к. Пусть 6.

/ = (В^п, У, У) — соответствующая этой библиотеке ЗИП типа Sbooi• Пусть U — произвольный граф из Ud{I^T). Если граф U — древовидный, то переобозначим его в U'. Если он недревовидный, то он — бесповторный. Следовательно, согласно теореме 24 существует древовидный граф U' € Ud{I, T) такой, что T (U) ^ T (U'), и мы перейдем к рассмотрению древовидного графа U'.

Возьмем произвольную запись у 6 V⁷. Согласно следствию 10 из теоремы 21 о существовании главных цепей, в графе V существует главная цепь С_у записи у. Для каждой записи из V выберем по главной цени и далее будем говорить только об этих главных цепях. Длина цепи С_у нс меньше чем га 4-г и каждому ребру этой цепи приписана некоторая переменная из характеристической функции записи у. Пусть у = Xi_xXi₂… Xj_m+r, где переменные упорядочены в порядке следования вдоль цепи С_у (если некоторая переменная встречается в цепи дважды и более, то упорядочиваем по первому вхождению). Сопоставим каждой переменной х^ (j G {l, m + г}) первое ребро, которому приписана эта переменная. Сложность этого ребра не меньше чем

Если ребро цепи С_у, соответствующее переменной Xi_Jt принадлежит также некоторой другой главной цепи С_у>, то все ребра, соответствующие переменным х*,…, х^_, также принадлежат цепи С_у>, так как граф U¹ — древовидный. Отсюда, учитывая, что любая пара записей из V имеет не более чем т — 1 общую переменную, получаем, что все ребра, соответствующие переменным х*_т,…, х"_т+г, принадлежат только одной главной цепи С_у. Таким образом, каждой записи из.

V мы можем сопоставить цепочку из т + 1 ребра, причем цепочки, соответствующие различным записям, не пересекаются. Суммарная Следовательно,.

Возьмем r (n) = [log_m+1(n/p)]. При таком выборе г.

т. е. выполняется условие (3.3).

Оценим величину г (п). Для этого, как и ранее, рассмотрим два случая: когда т = const, и тп —> оо при п —> оо.

В первом случае, используя (3.1), получим.

при п —> оо.

Во втором случае, используя (3.2), получим аналогичный результат.

при п —? оо. Откуда следует, что для любого графа U' € Ud (I_yT) при п —У 00

Следовательно, при п —> оо.

Построим некоторую ПИГ, который разрешал бы задачу I. Для этого возьмем граф описанный в теореме 27. Возьмем произвольную запись у € V. Пусть она равна Х{_хХ{₂… х_1т+г. Возьмем в графе U^-i вершину, на которой реализуется конъюнкция … х,_т-1

и выпустим из нее цепочку ребер, которым приписаны переменные • • • «^ж"т+г* И ^так проделаем для каждой записи у е V. Понятно, что полученный граф U над базовым множеством Т будет разрешать задачу I.

Подсчитаем сложность графа U. Поскольку он состоит из графа 1 и к цепочек, каждая из которых содержит г + 1 ребер, и сложность каждой из которых равна, как мы отмечали выше, 2²«^т(1 — — 2~^т~¹), то.

aside class="viderzhka__img" itemscope itemtype="http://schema.org/ImageObject">

Отсюда, учитывая неравенство (3.4), получаем Для завершения доказательства теоремы осталось заметить, что.

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