The Certifier's Bet

In AI safety verification, the choice of question is the lever. Call it the certifier's bet: which half of the safety problem you can solve depends entirely on which question you decide to formalize. The two halves look symmetric — sound certification (showing small input perturbations cannot change the network's answer) and complete certification (showing the input must move before the answer is forced to change) — but their complexity profiles invert.

A July 2026 preprint makes the asymmetry explicit. "Interval Certifications for Multilayered Perceptrons via Lattice Traversal" shows that, under the authors' interval definition, complete certifications admit a minimum solution in polynomial oracle calls, while the same question for sound certification is provably intractable. The mechanism generalizes: when verification feels hopeless, try the dual question. Instead of asking where the multilayered perceptron stays put, ask how far the input has to move to make it move. The lattice-traversal authors developed operators that walk an axis-aligned region until the input is forced across the decision boundary, and shipped an open-source tool called ParallelepipedoNN.

The unexplored side is where the polynomial algorithm lives.

The honest caveat is the lattice-traversal preprint's own. These guarantees hold under the authors' interval formulation; real-world inputs live in continuous space, and "complete minimality" is a formal property whose reach against practical robustness is not yet shown. The certifier's bet pays in theory. The cash register is still theoretical too.