Le vote des impairs : comment la différence symétrique accélère les automates ✛ ✎
Dans la salle d'audience, une chaîne de caractères est présentée en entrée. Douze jurés (les chemins de calcul) l'examinent symbole par symbole. Chacun peut déclarer « coupable » (accepter) ou « non coupable ». Pour un automate non déterministe ordinaire (NFA), un seul vote « pour » suffit. Mais dans un tribunal à différence symétrique (XNFA), le verdict est rendu selon la parité : si le nombre de votes « coupable » est impair, le mot est accepté. Un tel tribunal étrange, où la décision dépend de l'arithmétique des votes plutôt que de l'unanimité, change toute la stratégie algorithmique.
Le passage du demi-anneau booléen (OU/ET) au corps GF(2) (XOR/ET) semble une formalité, mais il déplace les problèmes dans une autre classe de complexité. L'acceptation d'un mot dans un NFA est complète pour la classe NL, tandis que dans un XNFA elle l'est pour ⊕L. La question de savoir si ces classes coïncident est un problème ouvert, comparable à celle-ci : peut-on transformer un tribunal d'un type en un tribunal de l'autre sans perdre la justice ? Le gain pratique, lui, vient d'une analyse fine du temps : pour les automates k-ambigus (où un mot a au plus k chemins-jurés), un algorithme dynamique a été développé, qui suit les états en effectuant seulement k|Q| opérations par symbole. Ici, |Q| est le nombre d'états, et k mesure l'ambiguïté.
Le plus surprenant est la réduction entre les modèles. Un NFA peut être transformé en un ensemble de k XNFA parallèles, en utilisant des poids aléatoires sur le corps GF($2^k$). L'analyse probabiliste garantit que si le NFA original accepte un mot, alors au moins un XNFA de l'ensemble rendra un verdict impair avec une erreur d'au plus 1/2. Cette astuce repose sur le lemme de Schwartz–Zippel, un classique de l'algèbre linéaire sur les corps finis. Il en résulte qu'un NFA polynomialement ambigu n'est pas plus difficile qu'un XNFA : si l'on trouve pour l'acceptation dans un XNFA un algorithme en temps O((|δ||w|)^{1-ε}), alors le NFA sera résolu presque aussi vite. C'est une contre-attaque contre l'hypothèse de Bringmann et al., qui affirmait que les NFA sont fondamentalement plus lourds.
Au final, la frontière entre les anneaux « faciles » et les demi-anneaux « difficiles » s'estompe. La structure de l'automate, son ambiguïté stochastique, s'avèrent être la clé pour accélérer les algorithmes et pour les bornes inférieures : tenter de prouver l'optimalité du temps cubique ($n^3$) pour ces problèmes via SETH exigerait de réfuter NSETH — une autre hypothèse non démontrée. Le tribunal automatisé, où les jurés votent selon la parité, n'est pas une simple exotisme, mais un outil qui nous rapproche de la compréhension de la frontière subtile entre les calculs polynomiaux et ultra-rapides. Le défi principal reste : lever l'exigence d'ambiguïté polynomiale. Alors, chaque déplacement de l'exposant ω de 3 vers 2 rapprochera le moment où la vérification de tout verdict deviendra presque quadratique — et la salle d'audience se videra, ne laissant qu'un calcul instantané.
Lors de la réduction d'un NFA à un ensemble de XNFA, la probabilité de manquer par erreur un mot accepté décroît comme |w|/$2^k$ : il suffit de prendre k = log|w| + 1 pour que l'erreur devienne inférieure à 1/2.
L'idée de la parité du nombre de chemins rappelle l'interférence quantique dans les mondes d'Everett : la particule suit tous les chemins à la fois, et le détecteur ne se déclenche que si leurs amplitudes s'additionnent de manière constructive.