Un mot — une chaîne de lettres — entre dans la salle d'audience. Douze jurés, chacun représentant un chemin de calcul, parcourent les lettres et décident : « accepter » ou « rejeter ». Dans un automate non déterministe classique, une seule voix « pour » suffit au mot. Mais il existe un tribunal étrange où le verdict dépend du nombre total de voix : si un nombre impair de jurés vote « pour », le mot est accepté. Cette règle a tout changé.

Pourquoi cela accélère-t-il les calculs ? Un automate classique utilise la logique « ou » : un chemin existe ou non. Ici, on utilise l'arithmétique des restes : chaque chemin vaut 0 ou 1, et le résultat global est leur somme modulo 2, c'est-à-dire un simple OU exclusif (addition sans retenue). Cette arithmétique permet d'appliquer des méthodes algébriques rapides et de suivre non pas tous les chemins, mais seulement leur nombre dans chaque état. Pour les automates où un mot n'a pas plus de k chemins, on a développé une astuce intelligente pour traiter chaque symbole en un nombre d'étapes proportionnel à k et à la taille de l'automate.

Le plus surprenant : on peut transformer un automate classique en un ensemble de plusieurs automates inhabituels. En utilisant des coefficients aléatoires et l'arithmétique des restes, on crée un ensemble tel que si l'automate d'origine acceptait le mot, au moins un des nouveaux donnera un résultat impair avec une probabilité supérieure à la moitié. Cela rappelle un jeu de devinette : au lieu d'un juge fiable, on prend une équipe d'excentriques, mais ensemble ils ne se trompent pas.

En fin de compte, la structure même de l'automate indique comment accélérer les calculs. L'ambiguïté aléatoire des chemins, qui gênait auparavant, devient une alliée. Et si les scientifiques prouvent qu'on ne peut pas faire plus vite, ils devront réfuter une autre hypothèse non démontrée. Le tribunal des voix impaires n'est pas qu'un amusement — c'est la clé de la frontière entre les calculs rapides et ultra-rapides.