Нижняя оценка сложности ИГ для задач поиска с коротким ответом и равномощными тенями записей

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

Дадим строгое определение исследуемого в данном разделе класса задач поиска.

Скажем, что ЗИП I = (X, V, р) обладает F-свойством, если она обладает A-свойством и для любых у, у' € V справедливо Р (0(у, р)) =.

= р (0№р)).

Обозначим.

Справедлива следующая теорема [24].

Теорема 7. Если I = {X, У, р) — ЗИП, обладающая F-свойством, Т — (F, 0) — измеримое базовое множество, допустимое для I, то

где у е V.

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

Лемма 3. Пусть 0 < t ^ ^ гпогда

Доказательство. Нетрудно убедиться, что R (k) есть непрерывная выпуклая функция, представляющая собой ломаную линию, причем точки З¹ и 2 • З¹ (/ = 0,1,2,…) являются точками излома. А из свойств выпуклых функций легко выводится утверждение леммы.

Обозначим через N — множество натуральных чисел, а через N₀ = N U {0}.

Доказательство. Из леммы 3 следует, что.

Пусть / = [log^k], с = к - 3^^{log3 к} т. е. к = 3* + с, где 0 ^ с ^ 2 • 3*, тогда по определению функции R (k)

Докажем утверждение леммы при четном к.

1) Пусть 0 < с ^ 3^Z₁, тогда.

так как в этом случае (3^Z₁ + с)/2 ^ 3^Z₁.

Для нечетного к лемма доказывается аналогично.

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

Следствие 2. Г (к) ^ R (k)-2-k, причем равенство достигается только при 4 • 3(«og₃*]-i k log3*l.

Доказательство. Из леммы 3 следует, что Докажем утверждение леммы при к = 3s.

Пусть I = [log₃ к], с = к — 3^^{1оКз к} т. е. к = 3* + с, к/3 = 3^/_1 + с/3.

1) Пусть 0 ^ с ^ 3*, тогда.

2) Пусть 3¹ ^ с ^ 2 • 3^Z, тогда.

Для случаев к = 3s+l и к = 3s-f 2 лемма доказывается аналогично.

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

Рассмотрим функцию M (D) = Y1 Р ' Фр-« ^гД^е D € Vo, Vq —

/зея (о) множество связных ориентированных деревьев с корнем, в которых каждое ребро принадлежит хотя бы одной цепи, ведущей из корня к какой-либо концевой вершине, р — количество концевых вершин, схемно достижимых из р.

Пусть N (k) = min{M (Z>): D € Vo и D = к}, где |.D| — количество концевых вершин в дереве D.

Дерево D € Vo назовем простым, если M (D) = iV (|?)|).

Лемма 6. Для любого натурального к существует простое дерево с к концевыми вершинами, полустепень исхода любой внутренней вершины которого равна либо 2, либо 3.

Доказательство. Предположим, что дерево D содержит ветвь D вида изображенного на рис. 2.1, где / ^ 4.

Рассмотрим дерево D₂ вида, указанного на рис. 2.2, где г = [//2].

Покажем, что M (D₂) ^ M (D).

Пусть U = Щ (i = М), U ^ 1.

Рис. 2.1. Ветвь с большой полустепенью исхода корня.

Рис. 2.2. Уменьшение полустепени исхода ветвей.

Возможны два случая:

1) / — четно, т. е. / = 2 • г, где г ^ 2, тогда.

причем равенство достигается лишь при г = 2.

2) I — нечетно, т. е. I = 2 • г + 1, где г ^ 2, тогда.

Таким образом, мы показали, что если в дереве есть ветвь вида Di, то ее всегда можно заменить на ветвь вида ?>2, и дерево от этого не усложнится.

Рис. 2.3. Ветвь с единичной полустепенью исхода корня.

Осталось заметить, что ветвь вида ?>з, изображенного на рис. 2.3, всегда можно заменить на ветвь Dt> не усложняя при этом дерева. Тем самым лемма доказана.

Доказательство. Доказывать будем индукцией по числу к. Базис индукции, k = 1; 7V (1) = 0 = Я (1). к = 2; N (2) = 4 = R (2). А: = 3; JV (3) = 9 = #(3).

Шаг индукции. Пусть для любого t < к выполнено N (t) = R (t).

Рис. 2.4. Дерево D.

Согласно лемме 6, существует простое дерево с к концевыми вершинами, которое имеет либо вид D_1? изображенный на рис. 2.4, либо вид ?>2> изображенный на рис. 2.5.

Рис. 2.5. Дерево D2.

Согласно предположению индукции, лемме 5 и следствию 2,.

С другой стороны, если D, D'₂, D'₃ — простые и такие, что их мощности (т. е. количество концевых вершин) различаются не более чем на 1, то M (D) = R (k) и D — простое, а если 4 • 3^^{log3 к}^~¹ ^ к ^ ^ 2−3(^1о*з*] _и D" и ?>2 — простые и такие, что ||I?i| — D₂ ^ 1, то M (Z>2) = R (k) и D₂ — простое дерево.

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

Перейдем к доказательству теоремы 7.

Возьмем произвольный ИГ U? U (I, F). Согласно теореме 6 существует такое информационное дерево D? V¹, что T (U) ^ T (D). Оценим сложность ИД D.

где у' некоторая запись из V.

В силу произвольности U теорема доказана.

Следствие 3. В условиях теоремы 7 где с ^ 3.

Справедливость утверждения следует из того, что k-Р (0(у, р)) ^ 1.

Для сравнения отметим, что мощностная нижняя оценка сложности, получаемая с помощью теоремы 4 для задач, обладающих Fсвойством, равна константе, которая не превышает 1.

Результат следствия 3 может показаться аналогичным теоретикоинформационной нижней оценке [121], но он имеет принципиальные отличия: во первых, он касается средней сложности, а не сложности в худшем случае, во-вторых, доказывался для произвольных сетей, а не бинарных деревьев.

Следствие 4. Если I = (X, У, р) — ЗИП, обладающая F-свойством, Т — (F, 0) — измеримое базовое множество, допустимое для I, такое, что Fq С F, то

Доказательство. Нижняя оценка следует из теоремы 7, а верхнюю даст ИД, изображенный на рис. 2.3, где Aj — простое дерево с к концевыми вершинами, которые одновременно являются листьями графа, нагрузка листьев записями из V выбрана произвольно, а нагрузка ребер осуществляется по методу, описанному в доказательстве теоремы б, так, чтобы выполнялось С-свойство.

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