Типичные значения ранга и длины ДНФ и эффект Шеннона

Эффект Шеннона для параметра ψ имеет место, если типичные значения ψ(f) для почти всех функций асимптотически совпадают с максимальной сложностью ψ(n). Для длины λ и ранга R ДНФ в курсе показано обратное: эффект Шеннона отсутствует.1

Хотя у почти всех f множество единиц имеет мощность \(|N_f|=2^{n-1}(1\pm O(n\cdot 2^{-n/2}))\), то есть совершенная ДНФ почти максимальна по длине, после минимизации для почти всех функций существуют ДНФ с \(\lambda(f)\le (3/4)\cdot 2^{n-1}(1+O(n\cdot 2^{-n/2}))\) и \(R(f)\le (3/4)\cdot n\cdot 2^{n-1}(1+O(n\cdot 2^{-n/2}))\).1

Что важно запомнить
  • Максимумы равны \(\lambda(n)=2^{n-1}\) и \(R(n)=n\cdot 2^{n-1}\).
  • У почти всех функций совершенная ДНФ имеет примерно \(2^{n-1}\) членов.
  • После минимизации для почти всех функций длина и ранг имеют верхние оценки примерно в 3/4 от соответствующих максимумов.1
  • Следовательно, типичная оптимальная сложность отделена от худшего случая, и эффекта Шеннона для λ и R нет.

Типичные значения и эффект Шеннона

Для параметра ψ рассматривают не только максимум ψ(n), но и интервал типичных значений, в который ψ(f) попадает для доли функций, стремящейся к 1 при n→∞. Если обе границы такого интервала асимптотически равны ψ(n), говорят об эффекте Шеннона.1

Почему совершенная ДНФ не показывает типичную минимальную сложность

Если значения случайной булевой функции на вершинах куба считать независимыми и равновероятными, то число её единиц концентрируется около \(2^{n-1}\). В лекциях это записано как

\(|N_f|=2^{n-1}(1\pm O(n\cdot 2^{-n/2}))\)

для почти всех f. Поэтому длина совершенной ДНФ почти у всех функций асимптотически равна \(2^{n-1}\). Но совершенная ДНФ не обязана быть оптимальной.1

Оценки после минимизации

Лемма 7.2 даёт для почти всех функций оценки

\(\lambda (f)\le (3/4)\cdot 2^{n-1}(1+O(n\cdot 2^{-n/2}))\),

\(R(f)\le (3/4)\cdot n\cdot 2^{n-1}(1+O(n\cdot 2^{-n/2}))\). 1

При этом функции Шеннона равны \(\lambda(n)=2^{n-1}\) и \(R(n)=n\cdot 2^{n-1}\). Таким образом, уже верхняя типичная оценка асимптотически отделена постоянным множителем от максимума. Этого достаточно, чтобы заключить: для длины и ранга ДНФ эффекта Шеннона нет.1

Важно понимать множитель 3/4 правильно. Лемма даёт верхнюю оценку для почти всех функций, а не утверждение, что типичная минимальная длина или ранг точно равны 3/4 соответствующего максимума.

Частые ошибки
  • Принимать коэффициент 3/4 за точное асимптотическое значение типичной минимальной сложности. В лекциях это верхняя оценка.
  • Смешивать длину совершенной ДНФ с минимальной длиной λ(f).
  • Считать отсутствие эффекта Шеннона утверждением о простоте всех функций. Оно сравнивает почти-всюду поведение с максимальным худшим случаем.

Другие вопросы

Источники

  1. 1 Ложкин С. А. Лекции по основам кибернетики Вариант 2017 г. (гр. 311–319), глава 1, §7, леммы 7.1–7.2, МГУ, факультет ВМК