Почему число вариантов ещё не определяет сложность поиска

Сложность поиска зависит от подсказок, цены попытки и шума в ответах.

Евгений Буянов - автор статьи, основатель проекта, преподаватель МГУ имени М.В. Ломоносова.

Почему число вариантов ещё не определяет сложность поиска

Дальше вы проверите это на 16 равновероятных секретах, сравните несколько подсказок и увидите, что меняют история и ошибки.

В статье вы узнаете:

Шестнадцать вариантов ещё не задают трудность

Представим секрет из четырёх двоичных знаков. Каждый знак равен 0 или 1, поэтому возможны 24 = 16 кодов: от 0000 до 1111. Все они пока равновероятны. Для домашнего опыта можно выбрать случайное число от 1 до 16, сопоставить числам коды и не показывать результат второму участнику.

Теперь изменим правило ответа. В первой версии ведущий говорит, угадан ли весь код. Во второй сообщает число знаков на правильных местах. В третьей показывает сами совпавшие позиции. Затем проведём те же поиски с видимой историей и без неё, а после добавим случайные ошибки в ответы. Пространство везде содержит те же 16 секретов, но путь к ним получается совсем разным.

Сложность поиска = пространство вариантов + цена попытки + обратная связь + шум

Это не арифметическая формула с одной единицей измерения, а схема проверки. Пространство сообщает, сколько кандидатов существует до начала. Цена попытки показывает, сколько времени, денег или риска стоит один тест. Обратная связь определяет, сколько кандидатов можно исключить после результата. Шум отвечает за вероятность, что подсказка обманет и часть работы придётся перепроверять.

Поэтому фраза «там всего 16 вариантов» почти ничего не обещает. С полным указанием совпавших позиций секрет можно раскрыть одним ходом. С ответом «не угадал» в худшем случае придётся проверять почти весь набор. А если ответ иногда неверен, даже найденный вариант ещё нужно подтвердить.

Хороший вопрос делит вероятность, а не список

Сначала оставим только честные ответы «да» и «нет». Первый вопрос звучит так: «секрет равен 0000?» Ответ «да» сразу завершит поиск, зато «нет» оставит 15 кандидатов. В худшем случае вопрос почти ничего не сделал.

Второй вопрос: «первые две двоичные цифры обозначают число меньше двух?» Для кодов 0000-0111 ответ будет «да», для 1000-1111 «нет». Обе ветви содержат по восемь секретов. Какой бы ответ ни пришёл, пространство уменьшится вдвое.

Разницу можно оценить двумя способами. Худший остаток после деления 1/15 равен 15, после деления 8/8 равен 8. Средний остаток тоже различается. Если размеры ветвей равны n1, n2 и так далее, а исходные варианты равновероятны, ожидаемое число оставшихся кандидатов считается так:

E⁡(R)=∑iniN ni=∑ini2N\displaystyle \operatorname{E}(R)=\sum_i\frac{n_i}{N}\,n_i=\frac{\sum_i n_i^2}{N}

N обозначает исходное число вариантов, ni размер ветви после конкретного ответа. Для вопроса 1/15 средний остаток равен (1² + 15²) / 16 = 14,125. Для вопроса 8/8 получается (8² + 8²) / 16 = 8. Редкий мгновенный успех первого вопроса не компенсирует огромную ветвь «нет».

Четыре последовательных деления пополам дают дерево 16 → 8 → 4 → 2 → 1. Значит, четырёх честных двоичных вопросов достаточно, чтобы гарантированно определить любой из 16 равновероятных секретов. Трёх недостаточно: у трёх вопросов существует не больше 23 = 8 разных цепочек ответов.

Балансировать нужно вероятность ветвей, а не только их размер. Если один секрет встречается в 60% случаев, вопрос о нём делит список 1/15, но вероятность 60/40. Такой вопрос уже может оказаться разумным. Равное деление по количеству оптимально для равновероятных кандидатов, одинаковой цены вопросов и надёжных ответов.

Один ответ может нести больше одного бита

Бит информации в этом контексте означает выбор между двумя равновероятными возможностями. Честный ответ на вопрос 8/8 даёт один бит: до ответа было 16 кандидатов, после осталось 8. Ответ «да» на вопрос 1/15 даёт сразу четыре бита и называет секрет, но случается только с вероятностью 1/16. Гораздо более частое «нет» даёт около 0,093 бита.

Среднюю информацию ответа можно посчитать по размерам получившихся групп:

I‾=∑iniNlog⁡2Nni\displaystyle \overline I=\sum_i\frac{n_i}{N}\log_2\frac{N}{n_i}

Для деления 1/15 получается около 0,337 бита, для 8/8 ровно один бит. Эту меру неопределённости Клод Шеннон сформулировал в теории связи: информативность зависит не от длины реплики, а от того, насколько она сокращает набор возможных сообщений. [Shannon, 1948]

Теперь попробуем код 0000 и попросим назвать число совпавших позиций. Возможны пять ответов: 0, 1, 2, 3 или 4 совпадения. Они делят 16 секретов на группы размером 1, 4, 6, 4 и 1. Самая большая ветвь содержит шесть кандидатов, средний остаток равен 4,375, а средняя информация ответа составляет примерно 2,031 бита.

Группа из шести появляется при двух совпадениях: нужно выбрать две позиции из четырёх, на которых останутся нули. Это число C(4, 2) = 6 можно проверить в калькуляторе сочетаний. Здесь порядок выбранных позиций не важен, поэтому перестановки дали бы ответ на другую задачу.

Если ведущий укажет не только число, но и сами совпавшие позиции, ответ станет структурированным. Для двоичного кода он раскроет весь секрет: совпавшая позиция содержит 0, несовпавшая 1. Получается 16 возможных рисунков ответа по одному на каждый код, то есть четыре бита за ход.

Количество формально возможных ответов задаёт только потолок. Пять исходов могут дать не больше log25 ≈ 2,322 бита, и то при одинаковой вероятности. В нашем примере среднее ниже, потому что ответ «два совпадения» встречается в шесть раз чаще крайних ответов. Много кнопок или длинная подсказка ещё не гарантируют полезную обратную связь. Важно, как именно она делит оставшиеся варианты.

История превращает отдельные подсказки в систему ограничений

Ответ полезен не только сам по себе. Он накладывает ограничение на секрет, а следующий ответ должен пересекаться со всеми предыдущими. После подсказки «в 0000 совпали две позиции» остаются шесть кодов. Новая попытка делит уже эту шестёрку, а не исходные 16 вариантов.

Если помнить только последний ответ, поиск каждый раз почти начинается заново. Именно поэтому полная история иногда ценнее более подробной одиночной подсказки. Она не добавляет новых фактов задним числом, зато не даёт выбросить уже полученные.

Эту механику удобно увидеть в игре «Быки и коровы». После попытки игра сообщает количество точных и неточных совпадений. Следующий кандидат должен давать те же результаты для каждой строки истории, а не только подходить к последней подсказке. Сама игра сложнее нашего двоичного примера, поэтому здесь важен общий принцип пересечения ограничений.

В задачах Эйнштейна история вынесена в матрицу. Галочка подтверждает связь, крест исключает её, а каждое новое условие распространяется по уже отмеченным строкам и столбцам. Матрица не делает подсказки умнее. Она сохраняет их последствия и освобождает рабочую память для следующего вывода.

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

Самый информативный вопрос может оказаться слишком дорогим

До сих пор каждый вопрос стоил одинаково. В жизни это редкость. Проверить, включён ли сервер, можно за секунду. Снять трассировку, воспроизвести ошибку на чистом устройстве или провести лабораторный анализ дольше и дороже. Стратегия должна сокращать неопределённость не за ход, а за минуту, рубль или единицу риска.

Допустим, точный тест сразу делит 16 причин на четыре равные группы, но занимает час. Дешёвый вопрос 8/8 занимает минуту. За тот же час можно задать несколько последовательных дешёвых вопросов и закончить раньше. В другой ситуации дорогой анализ предотвращает опасное решение, поэтому его цена оправданна. Само число бит не принимает решение за человека.

Шум добавляет ещё одну цену. Пусть ведущий отвечает «да» или «нет», но ошибается в 10% случаев. После четырёх вопросов уже нельзя считать найденную ветвь безусловно верной: один неверный ответ способен увести к другому секрету. Приходится повторять проверки, задавать перекрывающиеся вопросы или сохранять несколько вероятных кандидатов.

Для двоичного симметричного канала без памяти, где независимая ошибка с вероятностью q меняет каждый ответ на противоположный, теоретический предел полезной информации за один ответ равен:

C=1−H2(q),H2(q)=−qlog⁡2q−(1−q)log⁡2(1−q)\displaystyle C=1-H_2(q),\qquad H_2(q)=-q\log_2q-(1-q)\log_2(1-q)

При ошибке 10% предел составляет примерно 0,531 бита на ответ вместо одного. Это оценка пропускной способности для длинных кодированных сообщений, а не обещание найти наш секрет ровно за определённое число вопросов. Но направление она показывает честно: шумный ответ приходится оплачивать избыточностью.

Есть и человеческий шум. Формулировка может быть двусмысленной, измерение округлённым, оператор уставшим, а интерфейс способным скрыть часть результата. Перед усложнением алгоритма стоит проверить канал: одинаково ли люди понимают вопрос, можно ли повторить измерение и записана ли уверенность ответа.

Сначала посчитайте не названия, а состояния

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

Выбор без порядка. Из десяти кандидатов нужно назначить троих в одну одинаковую по роли группу. Состав «Анна, Борис, Вера» не меняется от перестановки имён. Здесь подходят сочетания, C(10, 3) = 120.

Распределение по разным местам. Те же три человека занимают роли председателя, секретаря и докладчика. Теперь порядок важен: Анна в роли председателя и Анна в роли докладчика дают разные состояния. Калькулятор размещений и перестановок покажет A(10, 3) = 720.

Последовательность с повторами. Наш двоичный код допускает два знака в каждой из четырёх позиций, поэтому вариантов 24 = 16. Для четырёх десятичных цифр с повторами получится 104 = 10 000. Если первая цифра не может быть нулём или повтор запрещён, пространство снова изменится.

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

Для федеральных цифровых систем США NIST SP 800-63B-4 требует сверять новый пароль с блок-листом распространённых, ожидаемых и скомпрометированных значений [NIST SP 800-63B-4, 2025]. Это требование относится к области действия документа, а не автоматически ко всем сервисам мира, но хорошо показывает практический вывод: одинаковые строки имеют разные априорные вероятности.

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

Наконец, уберите невозможные состояния до поиска. Если условие запрещает повтор, не нужно тестировать коды 0011 и 7777, будто они допустимы. Если система уже сообщила, что сумма двух параметров равна десяти, пары с другой суммой больше не входят в текущее пространство. Хорошая модель сокращает работу раньше хорошего вопроса.

Оцените поиск до запуска перебора

Перед первой попыткой полезно нарисовать маленькую карту задачи. Не обязательно считать энтропию до третьего знака после запятой. Достаточно последовательно ответить на семь вопросов:

  1. Что считается отдельным вариантом? Зафиксируйте порядок, повторы, ограничения и границы значений.
  2. Все ли варианты равновероятны? Если нет, оцените хотя бы крупные группы вероятности и начинайте с них.
  3. Сколько стоит попытка? Считайте время, деньги, вычисления, риск и возможность повторения.
  4. Какие ответы возможны? Выпишите не формулировки, а группы кандидатов, которые останутся после каждого ответа.
  5. Каков худший остаток? Большая ветвь показывает, что произойдёт при самом неудобном результате.
  6. Сохраняется ли история? Новый кандидат должен удовлетворять всем прежним ограничениям.
  7. Насколько надёжен ответ? Заранее решите, как подтверждать сомнительные измерения и противоречия.

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

Короткий вывод: число вариантов задаёт стартовый масштаб, но не длину пути. Поиск ускоряет не магический перебор, а вопрос, который дёшево и надёжно делит вероятные состояния, сохраняет прошлые ограничения и оставляет небольшую худшую ветвь. Иногда 16 вариантов раскрываются за один ответ. Иногда те же 16 приходится проверять почти по одному.

Есть что добавить?

Напишите своё мнение, комментарий или предложение.

ГлавнаяЖурнал расчётовПочему число вариантов ещё не определяет сложность поиска