Some Complexity Results for Robustness Verification for Binarized Neural Networks
arXiv:2606.18918
The paper analyzes the computational complexity of verification tasks for Binarized Neural Networks, proving NP-completeness for linear property satisfaction and non-uniform occlusion robustness, and presenting a polynomial-time algorithm for uniform occlusion robustness.
Abstract
This paper investigates the computational complexity of verification problems for Binarized Neural Networks (BNNs), in which activations and weights are binary. Specifically, we study three verification problems. First, we prove that checking the satisfiability of a linear property for a BNN is NP-complete via a reduction from the Boolean Satisfiability (SAT) problem. Second, we show that verifying robustness under non-uniform image occlusion is NP-complete through a reduction from SAT. Finally, we demonstrate that uniform occlusion induces a piecewise-constant structure in the network output, which enables the design of a polynomial-time algorithm for robustness verification.