Some Complexity Results for Robustness Verification for Binarized Neural Networks

arXiv:2606.18918v2 Announce Type: replace Abstract: This paper studies the computational complexity of verification problems for Binarized Neural Networks (BNNs), where activations (and sometimes weights) are binary. We analyze two problems: satisfiability and robustness under uniform image occlusion. We show that BNN satisfiability is NP-complete via a reduction from Boolean satisfiability problem (SAT), and that uniform occlusion induces a piecewise-constant structure in the network output, enabling a polynomial-time robustness-checking algorithm.

Related

• The Complexity of Verifying Feedforward Neural Networks in Quantised Settings
• Parameterized Hardness of Zonotope Containment and Neural Network Verification

Source: arXiv cs.LG | 2026-07-15