The Complexity of Verifying Feedforward Neural Networks in Quantised Settings
Eric Alsmann, Martin Lange, Marco Sälzer
Published in IJCAI/ECAI, 2026
We compare verification for rational, quantised, and dynamically quantised feedforward neural networks. For quantised networks with fixed arithmetic precision, verification is NP-complete with both linear constraints and bit-vector specifications. We also establish upper bounds for dynamically quantised networks, clarifying how arithmetic precision and the specification language affect complexity.