A word — a string of letters — walks into the courtroom. Twelve jurors, each a computational path, trace the letters and decide: 'accept' or 'reject'. In a standard nondeterministic automaton, one 'yes' vote is enough. But there's a peculiar court where the verdict depends on the total: if 'yes' gets an odd number of votes, the word is accepted. This rule changes everything.
Why does this speed up computation? A standard automaton uses OR logic: a path is either there or not. Here, we use modulo-2 arithmetic: each path is 0 or 1, and the overall result is their sum modulo 2 — that is, simple XOR (addition without carry). This arithmetic enables fast algebraic methods and lets us track not every path, but just how many there are in each state. For automata where a word has at most k paths, a clever technique processes each symbol in a number of steps proportional to k and the automaton's size.
Most surprising: you can turn a standard automaton into a set of unusual ones. Using random coefficients and modulo-2 arithmetic, we build an ensemble. If the original automaton accepted a word, at least one of the new ones yields an odd result with probability over a half. It’s like a game of guesswork: instead of one reliable judge, you recruit a team of eccentric ones, and together they never miss.
Ultimately, the very structure of the automaton hints at how to accelerate computation. Stochastic ambiguity of paths, once a hindrance, becomes a helper. And if scientists prove it can't be made any faster, they'll have to disprove another, unproven hypothesis. The odd-voting court is more than a curiosity — it's a key to the boundary between fast and ultrafast computing.
Take an automaton with a thousand states and at most 10 paths per word. The new algorithm reads a million-character word in a split second — hundreds of times faster than brute force.
In quantum mechanics, a particle also takes all paths at once, with the outcome determined by summing amplitudes. Here, it's summing votes modulo two.