  In this paper, we consider the computational complexity of formally verifying
the behavior of Rectified Linear Unit (ReLU) Neural Networks (NNs), where
verification entails determining whether the NN satisfies convex polytopic
specifications. Specifically, we show that for two different NN architectures
-- shallow NNs and Two-Level Lattice (TLL) NNs -- the verification problem with
(convex) polytopic constraints is polynomial in the number of neurons in the NN
to be verified, when all other aspects of the verification problem held fixed.
We achieve these complexity results by exhibiting explicit (but similar)
verification algorithms for each type of architecture. Both algorithms
efficiently translate the NN parameters into a partitioning of the NN's input
space by means of hyperplanes; this has the effect of partitioning the original
verification problem into polynomially many sub-verification problems derived
from the geometry of the neurons. We show that these sub-problems may be chosen
so that the NN is purely affine within each, and hence each sub-problem is
solvable in polynomial time by means of a Linear Program (LP). Thus, a
polynomial-time algorithm for the original verification problem can be obtained
using known algorithms for enumerating the regions in a hyperplane arrangement.
Finally, we adapt our proposed algorithms to the verification of dynamical
systems, specifically when these NN architectures are used as state-feedback
controllers for LTI systems. We further evaluate the viability of this approach
numerically.
