Complexity and Relaxation Limits: What the Barriers Actually Say

“Verification is hard” can refer to three different things: the worst-case complexity of a decision problem, the information lost by a chosen relaxation, or the cost of a particular implementation. They lead to different research questions and should not be used interchangeably.

Worst-case complexity is not an unconditional runtime law

Reachability is NP-complete even for restricted classes of neural networks; the precise representations and assumptions matter. See Sälzer and Lange.

For an NP-complete problem, a polynomial-time algorithm for all instances would imply $P=NP$. That is not a proof that every instance takes exponential time. Nor is it a proof that no algorithm can exploit structure, obtain useful certificates quickly, or improve substantially on current implementations.

For $k$ binary ReLU activation choices, there are at most $2^k$ assignments before checking feasibility. Some assignments are inconsistent with the input domain. Several can be eliminated together. A branch-and-bound method does not have to explicitly visit every assignment to return a sound answer.

Exactness and speed are not definitions of each other

A network whose activations are stable on a region reduces to an affine map there. Optimising a linear objective over a box or a suitable polytope can then be straightforward. A hard problem class contains easy instances.

Conversely, an incomplete algorithm is not automatically fast: it may solve a large relaxation or spend substantial time computing its bounds. Completeness describes what the method can resolve under its assumptions, not a measured runtime or the behaviour of a timeout-limited invocation.

A relaxation barrier depends on the relaxation

A single-ReLU triangle hull is the tightest convex description of that scalar graph over an interval. Using one such description per neuron does not make their composition the tightest description of a network’s joint behaviour.

The convex-relaxation barrier framework of Salman et al. makes the chosen family of relaxations explicit. Its conclusion should not be shortened to “no convex method can improve the bound.” Stronger constraints, different variable groupings or domain partitions change the problem being solved.

k-ReLU groups several ReLUs. Tjandraatmadja et al. retain a multivariate input structure for a single neuron. Those are distinct ways to retain information that a scalar interval description discards.

A concrete gap, not a slogan

For the network in the verification problem, $g(x)$ is exactly $1/4$. Independent triangle hulls nevertheless admit $x=0,h_1=0,h_2=1/2$, giving $g=-1/4$.

The scalar hulls are individually exact. Their joint relaxation has forgotten $h_1-h_2=x$. Adding that valid relation removes the gap for this example. Alternatively, splitting the input at zero fixes both ReLU states in each branch.

This example explains why solving the original relaxed LP more accurately cannot remove information that was not encoded. It also explains why changing the relaxation or partition can help.

What to ask when a claim sounds impossible

State the problem class and input encoding. State whether the claim is conditional on a complexity assumption. For a precision comparison, fix the domain, constraints, intermediate bounds and resource budget. For a measured bottleneck, identify which stage was timed.

There is no need to turn these distinctions into a universal ranking of intervals, zonotopes, symbolic bounds, LPs and SDPs. Their representations, transformers and optimisation procedures are not a single precision scale.

Key Takeaways

Worst-case hardness does not make every instance hard. Do not present a complexity assumption as an unconditional exponential lower bound.

A relaxation barrier has a scope. Stronger joint constraints or partitions may retain information the original relaxation lost.

Performance needs an identified cost. Encoding, bound construction and search are different parts of an implementation.

Next Phase

That is the end of Phase 1: Foundations. Phase 2 turns to the methods: how to construct a relaxation, what it costs, and where the information goes.

Further Reading

Salzer and Lange, “Reachability in Simple Neural Networks”, Fundamenta Informaticae 189(3-4); short version “Reachability is NP-Complete Even for the Simplest Neural Networks”, RP 2021 https://arxiv.org/abs/2203.07941.

Salman et al., “A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks”, NeurIPS 2019 https://arxiv.org/abs/1902.08722.

Singh, Ganvir, Pueschel and Vechev, “Beyond the Single Neuron Convex Barrier for Neural Network Certification”, NeurIPS 2019 https://proceedings.neurips.cc/paper/2019/hash/0a9fdbb17feb6ccb7ec405cfb85222c4-Abstract.html — this is k-ReLU, by Singh et al. rather than by Tjandraatmadja.

Tjandraatmadja et al., “The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification”, NeurIPS 2020 https://arxiv.org/abs/2006.14076.