  Neural networks with ReLU activation play a key role in modern machine
learning. In view of safety-critical applications, the verification of trained
networks is of great importance and necessitates a thorough understanding of
essential properties of the function computed by a ReLU network, including
characteristics like injectivity and surjectivity. Recently, Puthawala et al.
[JMLR 2022] came up with a characterization for injectivity of a ReLU layer,
which implies an exponential time algorithm. However, the exact computational
complexity of deciding injectivity remained open. We answer this question by
proving coNP-completeness of deciding injectivity of a ReLU layer. On the
positive side, as our main result, we present a parameterized algorithm which
yields fixed-parameter tractability of the problem with respect to the input
dimension. In addition, we also characterize surjectivity for two-layer ReLU
networks with one-dimensional output. Remarkably, the decision problem turns
out to be the complement of a basic network verification task. We prove
NP-hardness for surjectivity, implying a stronger hardness result than
previously known for the network verification problem. Finally, we reveal
interesting connections to computational convexity by formulating the
surjectivity problem as a zonotope containment problem
