Для отделимой по столбцам булевой таблицы с \(s\) различными состояниями длина любого тупикового диагностического теста \(t\) удовлетворяет резким границам \(\lceil\log_2 s\rceil\le t\le s-1\). Обе границы
Для почти всех больших отделимых по столбцам таблиц ситуация существенно лучше худшего случая: если \(\varphi(s)\to\infty\), то почти все такие таблицы имеют диагностический тест длины не более \(2\log_2 s+\varphi(s)\). Это почти-всюду верхняя оценка, а не точная формула типичного
Что важно запомнить
- Информационная нижняя граница: \(t\ge\lceil\log_2 s\rceil\).
- Для тупикового диагностического теста выполняется \(t\le s-1\), и эта граница
- Почти все большие отделимые по столбцам таблицы допускают тест длины примерно не более \(2\log_2 s\) с произвольно медленно растущей добавкой.
- Почти-всюду оценка является верхней оценкой минимальной длины, а не доказанным точным эквивалентом.
- Максимальное поведение и типичное поведение могут иметь совершенно разные порядки.
Универсальная нижняя граница
Если диагностический тест содержит \(t\) строк, каждый столбец после ограничения на эти строки превращается в двоичное слово длины \(t\). Таких слов не более \(2^t\). Чтобы различить \(s\) состояний, необходимо \(2^t\ge s\), откуда
\(t\ge\lceil\log_2 s\rceil.\)
Максимальная длина тупикового теста
Для любого тупикового диагностического теста отделимой по столбцам таблицы доказано \(t\le s-1\). Смысл доказательства можно увидеть через последовательное уточнение разбиения столбцов. Каждая строка тупикового теста необходима и должна разделять хотя бы один класс ранее неразличимых столбцов. Чтобы перейти от одного общего класса к \(s\) одноэлементным классам, требуется не более \(s-1\) существенных
В курсе показано, что обе универсальные границы достижимы на подходящих таблицах, поэтому улучшить их без дополнительных предположений нельзя.
Почти-всюду оценка
Пусть число доступных строк \(p(s)\) не меньше \(t(s)=\lceil2\log_2 s\rceil+\varphi(s)\), где \(\varphi(s)\to\infty\). Лемма курса утверждает: у почти всех отделимых по столбцам таблиц первые \(t(s)\) строк уже образуют диагностический
Следовательно, для почти всех таких таблиц минимальная длина диагностического теста не превосходит \(2\log_2 s+\varphi(s)\). Вместе с универсальной нижней границей это показывает сильный разрыв между линейным худшим случаем \(s-1\) и логарифмическим поведением подавляющего большинства таблиц. Однако из приведённой теоремы не следует точная асимптотика минимальной длины с коэффициентом 2.
Пример простыми словами
Пусть \(s=2^m\). Тогда информационная нижняя граница равна \(m\), а универсальная верхняя граница для тупикового диагностического теста равна \(2^m-1\). Для почти всех больших отделимых по столбцам таблиц теорема даёт существенно меньшую оценку на минимальный тест: не более \(2m+\varphi(2^m)\), где \(\varphi(s)\to\infty\) сколь угодно медленно. Так на одном примере видно различие между худшим случаем и почти-всюду поведением без подмены асимптотической теоремы конечным числом.
Частые ошибки
- Принимать \(2\log_2 s\) за точное типичное значение минимального теста. В курсе это почти-всюду верхняя оценка с добавкой \(\varphi(s)\to\infty\).
- Смешивать максимальную длину тупикового теста \(s-1\) с минимальной длиной теста конкретной таблицы.
- Забывать условие отделимости столбцов: функционально неразличимые состояния сначала нужно объединить.
