В зал суда входит слово — цепочка букв. Двенадцать присяжных, каждый из них — вычислительный путь, идут по буквам и решают: «принять» или «отклонить». В обычном недетерминированном автомате слову достаточно одного голоса «за». Но есть странный суд, где вердикт зависит от общего числа голосов: если «за» проголосовало нечётное число присяжных, слово считается принятым. Это правило изменило всю работу.

Почему это ускоряет вычисления? Обычный автомат использует логику «или»: путь либо есть, либо нет. Здесь же работает арифметика остатков: каждый путь — это 0 или 1, а общий результат — их сумма по модулю 2, то есть простое исключающее ИЛИ (сложение без переноса). Такая арифметика позволяет применить быстрые алгебраические методы и следить не за всеми путями, а только за тем, сколько их в каждом состоянии. Для автоматов, где у слова не больше k путей, разработан умный способ обрабатывать каждый символ за число шагов, пропорциональное k и размеру автомата.

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

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