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

Эффект Шеннона для параметра \(\psi\) имеет место, если типичные значения \(\psi (f)\) для почти всех функций асимптотически совпадают с максимальной сложностью \(\psi (n)\). Для длины \(\lambda\) и ранга 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
  • Следовательно, типичная оптимальная сложность отделена от худшего случая, и эффекта Шеннона для \(\lambda\) и R нет.

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

Для параметра \(\psi\) рассматривают не только максимум \(\psi (n)\), но и интервал типичных значений, в который \(\psi (f)\) попадает для доли функций, стремящейся к 1 при \(n\to\infty\). Если обе границы такого интервала асимптотически равны \(\psi (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 за точное асимптотическое значение типичной минимальной сложности. В лекциях это верхняя оценка.
  • Смешивать длину совершенной ДНФ с минимальной длиной \(\lambda (f)\).
  • Считать отсутствие эффекта Шеннона утверждением о простоте всех функций. Оно сравнивает почти-всюду поведение с максимальным худшим случаем.

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

Источники

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