Imagine you're a building inspector. Checking whether a single door locks properly is one job. Checking whether any door in the building could be opened by any key from a ring of master keys is a fundamentally harder job — you can't reduce it to checking doors one at a time. Adrian Wurm's paper makes exactly this kind of structural separation precise for neural network security properties, and the result is a clean complexity-theoretic map that tells you which verification problems are tractable neighbors of each other and which live on entirely different floors of the computational hierarchy. The core claim: eight security-relevant properties of piecewise-linear networks (ReLU and friends) can be classified by their quantifier-alternation structure. Because the function computed by such a network is definable by a quantifier-free formula over real addition whose size is linear in the network, every property becomes a sentence in the polynomial hierarchy at the level determined by its quantifier prefix. This is the paper's organizing trick — it converts neural network verification questions into sentences and reads off their complexity from Sontag's 1985 theorem. The move is elegant and surprisingly productive. The headline results: non-interference, monotonicity, and counterfactual fairness are co-NP-complete — same level as interval verification and network equivalence. These are 'one-quantifier' properties. Backdoor detection from a quantised alphabet is Σ₂ᴾ-complete, sitting one full level above robustness certification. This means you cannot reduce backdoor detection to polynomially many robustness queries unless the polynomial hierarchy collapses — a separation most complexity theorists consider extremely unlikely. Inversion resistance (can an attacker recover private inputs?) is co-NP-complete for every lₚ metric with p a fixed positive integer. The most striking finding involves parameter quantification. When you move from asking 'does a bad input exist?' to 'does a bad parameter configuration exist?' — the model for bit-flip attacks, radiation-induced faults, and analog accelerator noise — verification jumps to ∃ℝ-complete. This holds even for networks consisting entirely of identity nodes, where every previously studied problem is in P. Confining each parameter to a box of inverse-polynomial width doesn't help. The safety dual (∀ℝ-complete for ReLU) is equally hard. This is a genuine wall: parameter-space verification is not just harder in practice, it's provably in a different complexity class. The method is pure complexity theory — no experiments, no heuristics, no benchmarks. Membership results follow from the quantifier-prefix observation; hardness results come from reductions. The paper builds on Sontag (1985), the Katz et al. (2017) co-NP-completeness of ReLU robustness, and the Schaefer–Štefankovič theory of ∃ℝ. The key technical requirement the paper makes explicit: these membership results need the quantified objects to be inputs, not parameters. Once you quantify over parameters, you leave the polynomial hierarchy entirely. What this means for practitioners: if you're building a verification tool for deployed neural networks, this paper tells you which problems your tool can hope to solve efficiently (robustness, fairness, monotonicity — all co-NP) and which ones require fundamentally different approaches (backdoor detection, parameter-fault safety). The Σ₂ᴾ-completeness of backdoor detection is particularly important because it formally kills the hope that you could certify a model as backdoor-free by running a polynomial number of robustness checks. You need a qualitatively different verification strategy. The paper is 26 pages of clean mathematical argument with no experimental component. It does not propose algorithms or run benchmarks — it draws the map that tells algorithm designers where to dig and where the bedrock is. This is foundational work in the literal sense: it establishes what is and isn't possible before anyone writes a line of verification code.
