The Odd-Jury Automaton: How Symmetric Difference Speeds Up Computation ✛ ✎
In the courtroom, a string is presented as input. Twelve jurors (computation paths) examine it symbol by symbol. Each can render a 'guilty' (accept) or 'not guilty' verdict. For a conventional nondeterministic automaton (NFA), one 'yes' vote suffices. But in a symmetric-difference court (XNFA), the verdict depends on odd parity: if the number of 'guilty' votes is odd, the word is accepted. This peculiar court, where the decision hinges on vote arithmetic rather than unanimity, upends the entire algorithmic strategy.
Shifting from the Boolean semiring (OR/AND) to the field GF(2) (XOR/AND) might seem a formality, but it recasts problems into a different complexity class. Word acceptance in NFA is complete for NL, while in XNFA it's complete for ⊕L. Whether these classes coincide remains open — akin to asking: can one type of court be remodeled into another without compromising justice? Practical gains come from fine-grained analysis of running time: for k-ambiguous automata (where a word has at most k juror paths), a dynamic algorithm tracks states, performing only k|Q| operations per symbol. Here, |Q| is the number of states, and k the measure of ambiguity.
The most surprising twist is the reduction between models. An NFA can be transformed into an ensemble of k parallel XNFAs using random weights over GF($2^k$). Probabilistic analysis guarantees that if the original NFA accepts a word, at least one XNFA in the ensemble will yield an odd verdict with error probability at most 1/2. This trick relies on the Schwartz–Zippel lemma — a classic of linear algebra over finite fields. It implies that a polynomially ambiguous NFA is no harder than an XNFA: if an algorithm can decide XNFA acceptance in time O((|δ||w|)^{1-ε}), then NFA can be solved almost as fast. This serves as a countermove to Bringmann et al.’s conjecture that NFA is strictly harder.
Thus, the line blurs between 'easy' rings and 'hard' semirings. The structure of an automaton, its stochastic ambiguity, become the key to faster algorithms and lower bounds: attempting to prove optimality of cubic time ($n^3$) for these tasks via SETH would demand disproving NSETH, yet another unproven hypothesis. The automaton court, where jurors vote by parity, is not mere whimsy but a tool that edges us closer to understanding the fine boundary between polynomial and ultra-fast computation. The grand challenge remains: lifting the requirement of polynomial ambiguity. Then each shift of the exponent ω from 3 toward 2 would bring us nearer to the moment when checking any verdict becomes almost quadratic, and the courtroom empties, leaving only instantaneous calculation.
When reducing an NFA to an XNFA ensemble, the probability of mistakenly skipping an accepting word drops as |w|/$2^k$: it’s enough to set k = log|w| + 1 to make the error less than 1/2.
The idea of path parity evokes quantum interference in Everettian worlds: a particle traverses all paths at once, but a detector clicks only if the amplitudes combine constructively.