Complexity of Reachability Problems in Neural Networks

arXiv:2306.05818 · cs.CC · Submitted 2023-06-09 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Complexity of Reachability Problems in Neural Networks".

Jane: Here's the gist of the paper. In this paper we investigate formal verification problems for Neural Network computations <ref:2306.05818#pg3>.

Tom: The reachability problem is in P for linear activations, in NP for semilinear activations, NPhard for all non-linear activations that are continuous on an interval, and ETRhard for several commonly used activations such as arctan and the exponential function <ref:2306.05818#pg4>.

Jane: Reachability Problem Definition The problem under consideration involves deciding whether a valid input exists such that the network’s result on that input is a valid output <ref:2306.05818#pg4>.

Tom: For a feedforward neural network N, this is defined by two Linear Programming instances, one for the input variables and one for the output variables <ref:2306.05818#pg5>.

Title and authors: Tom: Now let's look at the formal summary of "Complexity of Reachability Problems in Neural Networks" and what that actually boils down to for us.

Jane: It’s basically about defining a reachability question for a feedforward neural network as two linear programming instances, one for inputs and one for outputs.

Lu: The core task is deciding if there exists any valid input such that the network computes an output within the set of valid outputs specified by the problem.

Meng: So, it’s asking: can we find an input that satisfies both the network's internal computation rules and those external constraints?

Tom: That leads to them linking this reachability problem to Constraint Satisfaction Problems, showing a linear time equivalence between them.

Jane: They establish this by expressing the network's input and output specifications as constraints in a specific type of constraint satisfaction problem.

Lu: This connection allows them to classify activations based on how they fit into these constraint satisfaction frameworks, giving us that classification we talked about earlier.

Meng: So it’s a structural way of looking at why some functions are easy to verify and others are incredibly hard.

Tom: It gives us the framework to systematically categorize the computational difficulty based on those activation functions we discussed in segment one.

Jane: So, if you pick an activation function that falls into one of these classes, you immediately know whether you’re looking at P, NP complete, or ETR hard problems.

Lu: It’s about using these constraint satisfaction tools to build a formal language for describing the network's behavior and its constraints.

Meng: I like that part where they show how input and output specifications can be expressed as constraints in that problem structure. It makes the complexity tangible, not just abstract theory.

Tom: It moves us from saying "this is hard" to showing *why* it’s hard based on the mathematical structure of the functions involved.

Jane: And they really lay out a clear hierarchy for different classes of functions, which is super useful when designing systems where verification speed matters.

The paper's summary: Tom: The authors point out some things they did to make the analysis more rigorous and to push the results further.

Jane: They added a theorem showing that for any set of unary real functions, both the Constraint Satisfaction Problem and the NNReach problem are linear time equivalent.

Lu: This equivalence is established by mapping input and output specifications directly into a set of constraints using corresponding variables.

Meng: That’s a lot of work to prove that mapping works consistently across all those different function types, which is where the machinery gets heavy.

Tom: It solidifies the link between the problem on one side and the other, making it less of a loose comparison and more of a formal equivalence.

Jane: They also established that for network equivalence problems, Network Equivalence one-one reduces to the complement of reachability problems in linear time when F includes functions like identity or ReLU.

Lu: That reduction is key because it lets us check if two different network architectures compute the same function by testing if they *don't* compute the same output.

Meng: So, instead of trying to prove they are equal, you just try to find a counterexample where one produces something the other doesn't. That’s a pragmatic approach for deployment.

Tom: It gives us a concrete way to check equivalence efficiently for those specific activation functions we mentioned earlier.

Jane: It shows that when you have those specific functions, the verification task isn't just theoretically hard; it becomes tractable in linear time for equivalence checks.

The paper's improvements: Tom: So wrapping up the "Complexity of Reachability Problems in Neural Networks," we see that the complexity hinges entirely on which activation function you choose for your neural network.

Jane: The key thing to remember is that linear activations are in P, semilinear ones are in NP, and general continuous non-linear ones are NPhard.

Lu: And for those specific hard cases like polynomials or exponentials, the problem lands in the Existential Theory of the Reals class.

Meng: So for production systems using those functions, you should expect significant verification hurdles unless you're dealing with very constrained scenarios where it stays in P or NP.

Tom: The practical implication is that when designing a network, you need to be super careful about the function family you select if your goal is fast verification.

Jane: And this paper gives us the formal tools to understand *why* those different functions have different computational costs, which helps guide our design choices.

Lu: For future work, they're still looking at things like whether there are any activation functions that aren't semilinear but still result in a reachability problem in NP.

Meng: And we should probably keep pushing for those lower bounds on the ETR hardness results because those are the hardest problems to verify and understand.

Tom: Exactly. It’s a lot of work, but understanding this landscape helps us decide which verification methods are worth investing in where they will actually make a difference.

Conclusion: Tom: So, what we just heard is about the complexity of reachability problems in neural networks. Basically, they’re showing us how hard it is to figure out if any input can actually produce a valid output given a network's rules and constraints.

Jane: It boils down to checking if there's an input that satisfies both the network's internal computation and the required final output conditions.

Lu: They use constraint satisfaction problems to link this reachability problem, which lets them classify different types of neural network functions in terms of complexity classes like P or NP hard.

Meng: For those tricky functions like ReLU or Signum, they’re showing that if you try to verify them quickly, you’re going to run into NP complete problems unless P equals NP.

Lalam: I'm sure the formal proof linking the reachability problem to constraint satisfaction is solid; it gives a very clear way to map network structure onto those mathematical constraints.

Tom: And they also proved that for equivalence problems, if you include functions like identity or signum in your set, you can check if two networks are equivalent in linear time. That's pretty useful for deployment.

Jane: It means we don't have to do a full deep dive just to see if two different network designs compute the same thing; we can test it quickly with those specific functions.

Lu: The existential theory of the reals part is also interesting; it shows that for certain complex functions, like any non-linear polynomial, you’re looking at ETR hardness, which sets a lower bound on how hard these problems are to solve.

Meng: That ETR hardness suggests that when you move into even more complicated models or functions, the verification costs grow very fast. It gets much harder to keep up with things at scale.

Tom: So for anyone building a system right now, the message is clear: know your activation function; it dictates how hard the verification will be.

Jane: Exactly. The paper on "Complexity of Reachability Problems in Neural Networks" gives us a roadmap for understanding exactly where we are standing computationally when dealing with deep learning models.

Lu: It’s a solid piece of work because it formalizes the connection between network structure and computational difficulty in a way that is very hard to ignore.

Meng: Anyway, this whole thing makes me think about how we actually deploy these things; if verification takes too long, you just don't ship it.

Lalam: I'm confident this paper provides a strong foundation for understanding the verification landscape in neural networks moving forward.

BTU Cottbus-Senftenberg, Lehrstuhl Theoretische Informatik

cs.CC

Submitted: 2023-06-09

Updated: 2023-06-09

Comments: 20 pages, no figures

Journal ref: RP 2023, Lecture Notes in Computer Science 14235 (2023) 15-27

DOI: 10.1007/978-3-031-45286-4_2

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

Importance score: 77/100

The gist: In this paper we investigate formal verification problems for Neural Network computations <ref:2306.05818#pg3>.

Key concepts

Reachability Problem
This problem asks if there is an input to a neural network that produces a specific desired output. It is formally defined using two Linear Programming instances, and its complexity depends entirely on the network's activation function.
Constraint Satisfaction Problems (CSP)
The paper links reachability problems to CSPs. This connection allows researchers to classify the difficulty of neural network verification by translating input and output specifications into sets of constraints within a CSP framework.
Activation Functions
The type of function used in a neural network, like linear, semilinear, or non-linear continuous functions (e.g., ReLU), dictates the complexity class of the reachability problem. Different functions lead to different levels of computational difficulty.

Terminology

Summary

In this paper we investigate formal verification problems for Neural Network computations <ref:2306. p. 1

Where the paper says it

de/ wurm@b-tu. de Abstract: In this paper we investigate formal verification problems for Neural Network computations.

05818#pg3>. The reachability problem is in P for linear activations, in NP for semilinear activations, NPhard for all non-linear activations that are continuous on an interval, and ETRhard for several commonly used activations such as arctan and the exponential function <ref:2306. p. 2
Where the paper says it

In the present work we study the reachability problem for commonly used activation functions and show that for most of them it will be complete either in (classical) NP or in the presumably larger class ∃R, which captures the so-called existential theory of the reals. Our main results are as follows: The reachability problem is in P for linear activations, in NP for semilinear activations, NPhard for all non-linear activations that are continuous on an interval, and ETRhard for several commonly used activations such as arctan and the exponential function.

05818#pg4>.

Reachability Problem Definition

The problem under consideration involves deciding whether a valid input exists such that the network’s result on that input is a valid output <ref:2306.05818#pg4>. For a feedforward neural network N, this is defined by two Linear Programming instances, one for the input variables and one for the output variables <ref:2306. p. 3

Where the paper says it

a) Let F be a set of activation functions from R to R. An instance of the reachability problem for neural networks NNReach(F) consists of an n ∈ N, a (feedforward) neural network N with n inputs and all its activation functions belonging to F, rational data as weights and biases, and two instances of LP in decision version with rational data, one with the input variables of N as variables, and the other with the output variables of N as variables.

05818#pg5>. The size of an instance is given as the sum of the (usual) bit-sizes of the two LP instances and T · L <ref:2306. p. 4
Where the paper says it

Then the Network Equivalence problem NE(F) is the decision problem whether two F-networks describe the same function or not. d) The size of an instance is given as the sum of the (usual) bit-sizes of the two LP instances and T · L; here, T denotes the number of neurons in the net N and L is the maximal bit-size of any of the weights and biases.

05818#pg5>.

Complexity via Constraint Satisfaction Problems

The analysis links these reachability problems to Constraint Satisfaction Problems (CSP) <ref:2306.05818#pg8>. Theorem 2 states that for any set of unary real functions F = f1, …, fs, CSP(R; ≤, R+, R=1, f1, …, fs) and NNReach(id, f1, …, fs) are linear-time equivalent <ref:2306. p. 5

Where the paper says it

Consider as domain the real numbers R, together with the binary order relation ≤, the ternary relation R+ defined via R+(x, y, z) ⇔ x + y = z, and the unary relation R=1(x) ⇔ x = 1. Then CSP(R; ≤, R+, R=1) is polynomial time equivalent to the Linear Programming problem in feasibility form with rational input data.

05818#pg9>. This equivalence is established by showing that input and output specifications of N can be expressed as a set of constraints in CSP(R; ≤, R+, R=1) using corresponding variables <ref:2306. p. 7
Where the paper says it

Wurm input and output specifications of N can be expressed as a set of constraints in CSP(R; ≤, R+, R=1) using the corresponding variables, which is of linear size with respect to the size of those specifications. For the nodes in the hidden layers, we proceed similarly.

05818#pg10>.

Classification of Activation Functions

The paper provides several complexity results based on the activation functions used <ref:2306.05818#pg5>.

(i) Linear activations:

The reachability problem is in P for linear activations <ref:2306.05818#pg4>.

(ii) Semilinear activations:

The reachability problem is in NP for semilinear activations <ref:2306.05818#pg5>.

(iii) All non-linear continuous activations:

The reachability problem is NPhard for all non-linear activations that are continuous on an interval <ref:2306.05818#pg5>.

(iv) Specific NP-hard cases:

The paper shows that the reachability problem is NP-complete for frequently used activations such as (Leaky) ReLU, Heaviside and Signum <ref:2306.05818#pg5>.

Hardness Results for Non-linear Functions

Theorem 3 establishes that NNReach(id, f) is NP-hard for any non-linear function f: R → R that is continuous on an interval [a, b] ⊆ R <ref:2306.05818#pg12>. This hardness is shown by constructing a primitive positive function ¯f that excludes an interval witnessed by two rational points <ref:2306. p. 9

Where the paper says it

NNReach(id, f) is NP-hard for any non-linear function f : R → R that is continuous on an interval [a, b] ⊆ R, including f(x) = x 1+e−x and all sigmoidal functions such as f(x) = 1 1+e−x , f(x) = √ x 1+x2 and f(x) = tanh(x) the hyperbolic tangent. By the previous Corollary, it suffices to show that with such a function f we can pp-define a new function ¯f that excludes an interval witnessed by two rational points.

05818#pg18>. Furthermore, NNReach(id, f) is ETR-complete for any non-linear polynomial and ETR-hard for the exponential function and various sigmoidal functions <ref:2306. p. 1
Where the paper says it

The former question’s complexity has been investigated recently in [20] by S¨alzer and Lange for nets using the Rectified Linear Unit and the identity function as their activation functions. We complement their achievements by showing that the problem is NP-complete for piecewise linear functions with rational coefficients that are not linear, NP-hard for almost all suitable activation functions including non-linear ones that are continuous on an interval, complete for the Existential Theory of the Reals ∃R for every non-linear polynomial and ∃R-hard for the exponential function and various sigmoidal functions.

05818#pg5>.

Equivalence of Verification Problems

The paper studies the complexity of verification problems like Network Equivalence (NE) and Interval Property Verification (VIP) <ref:2306.05818#pg10>. Theorem 5 shows that NE(id) is in P, while NE(ReLU) is co-NP-complete and NE(f) is co-NP-hard for any non-linear f that is continuous on an interval <ref:2306. p. 9

Where the paper says it

We will now see a much more powerful version of the NP-hardness part of Corollary 1: Theorem 3. NNReach(id, f) is NP-hard for any non-linear function f : R → R that is continuous on an interval [a, b] ⊆ R, including f(x) = x 1+e−x and all sigmoidal functions such as f(x) = 1 1+e−x , f(x) = √ x 1+x2 and f(x) = tanh(x) the hyperbolic tangent.

05818#pg14>. Similarly, VIP(id) is in P and VIP(ReLU) is in co-NP <ref:2306. p. 4
Where the paper says it

Complexity of Reachability Problems in Neural Networks 5 problem is to decide if there exists an x ∈ R n that satisfies the input specification such that the output N(x) satisfies the output specification. b) The problem verification of interval property VIP(F) consists of the same instances, except for the output specification being the open polyhedron, meaning the interior of the solution space.

05818#pg15>. Theorem 7 shows that NE(F) one-one reduces to VIP(F) in linear time when F contains id or ReLU and H or sign <ref:2306. p. 9
Where the paper says it

Moreover, if we use the strong version that requires semilinearity, we get that NNReach(id, f) is NP-complete for f being either the absolute value, the floor or ceiling function on a bounded domain, the sign or the Heaviside function, piecewise linear functions such as fα(x) =    −1 if x ≤ −α x α if − α < x < α 1 if x ≥ α , the ReLU function, Leaky ReLU given via Rα(x) = x if x ≥ 0 αx if x < 0 , α ∈ Q as well as all their scalar generalizations and any other non-trivial rational step function such as the indicator function on an interval. We will now see a much more powerful version of the NP-hardness part of Corollary 1: Theorem 3.

05818#pg15>.

Existential Theory of the Reals Complexity

Theorem 4 provides results concerning the complexity class ∃R for NNReach problems <ref:2306.05818#pg13>. For any non-linear polynomial, NNReach(id, f) is ∃R-complete and ETR-hard for functions like ELU(x) and f(x) = e−x <ref:2306. p. 1

Where the paper says it

The former question’s complexity has been investigated recently in [20] by S¨alzer and Lange for nets using the Rectified Linear Unit and the identity function as their activation functions. We complement their achievements by showing that the problem is NP-complete for piecewise linear functions with rational coefficients that are not linear, NP-hard for almost all suitable activation functions including non-linear ones that are continuous on an interval, complete for the Existential Theory of the Reals ∃R for every non-linear polynomial and ∃R-hard for the exponential function and various sigmoidal functions.

05818#pg20>. This implies that the reachability problem for the sigmoid function may be related to ETR <ref:2306. p. 2
Where the paper says it

If, for example, the typical sigmoid activation f(x) = 1/(1 + e −x ) is used, it has to be specified in which sense it is computed by the net: For example exactly or approximately, and at which costs these operations are being performed. In the present work we study the reachability problem for commonly used activation functions and show that for most of them it will be complete either in (classical) NP or in the presumably larger class ∃R, which captures the so-called existential theory of the reals.

05818#pg20>.

Open Questions and Future Directions

The paper concludes by listing several open questions regarding the complexity of these problems <ref:2306.05818#pg21>. These include whether there exist activation functions that are not semilinear but still lead to a reachability problem in NP, or if the reachability problem for the sigmoid function can be classified better than just as NP-hard <ref:2306. p. 2

Where the paper says it

In the present work we study the reachability problem for commonly used activation functions and show that for most of them it will be complete either in (classical) NP or in the presumably larger class ∃R, which captures the so-called existential theory of the reals. Our main results are as follows: The reachability problem is in P for linear activations, in NP for semilinear activations, NPhard for all non-linear activations that are continuous on an interval, and ETRhard for several commonly used activations such as arctan and the exponential function.

05818#pg21>. The paper also questions how these problems behave in models of real computations like the BlumShub-Smale model <ref:2306. p. 1
Where the paper says it

de/ wurm@b-tu. de Abstract: In this paper we investigate formal verification problems for Neural Network computations.

05818#pg21>.

References

The references listed are [1] through [20] <ref:2306.05818#pg15>. The survey of deep learning techniques for autonomous driving is reference [9] <ref:2306. p. 1

Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

05818#pg15>. The textbook concerning structural issues related to Deep Neural Networks is provided by [5] <ref:2306. p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

05818#pg15>. The survey of recent architectures of deep convolutional neural networks is reference [14] <ref:2306. p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

05818#pg15>. The imageNet Classification with Deep Convolutional Neural Networks is reference [15] <ref:2306. p. 1
Where the paper says it

For the completeness results, linking the verification tasks with the theory of Constraint Satisfaction Problems turns out helpful. 1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty.

05818#pg15>. The survey on deep learning in medical image analysis is reference [16] <ref:2306. p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

05818#pg15>. The survey of safety and trustworthiness of deep neural networks is reference [19] <ref:2306. p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

p. 1
Where the paper says it

[14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5]. Among the many different aspects of areas where the use of Neural Networks seems appropriate, some also involve safety-critical systems like autonomous driving or power grid management.

05818#pg15>. The new polynomial-time algorithm for linear programming is reference [12] <ref:2306. p. 5
Where the paper says it

Consider as domain the real numbers R, together with the binary order relation ≤, the ternary relation R+ defined via R+(x, y, z) ⇔ x + y = z, and the unary relation R=1(x) ⇔ x = 1. Then CSP(R; ≤, R+, R=1) is polynomial time equivalent to the Linear Programming problem in feasibility form with rational input data.

p. 5
Where the paper says it

Consider as domain the real numbers R, together with the binary order relation ≤, the ternary relation R+ defined via R+(x, y, z) ⇔ x + y = z, and the unary relation R=1(x) ⇔ x = 1. Then CSP(R; ≤, R+, R=1) is polynomial time equivalent to the Linear Programming problem in feasibility form with rational input data.

p. 5
Where the paper says it

Consider as domain the real numbers R, together with the binary order relation ≤, the ternary relation R+ defined via R+(x, y, z) ⇔ x + y = z, and the unary relation R=1(x) ⇔ x = 1. Then CSP(R; ≤, R+, R=1) is polynomial time equivalent to the Linear Programming problem in feasibility form with rational input data.

p. 5
Where the paper says it

Consider as domain the real numbers R, together with the binary order relation ≤, the ternary relation R+ defined via R+(x, y, z) ⇔ x + y = z, and the unary relation R=1(x) ⇔ x = 1. Then CSP(R; ≤, R+, R=1) is polynomial time equivalent to the Linear Programming problem in feasibility form with rational input data.

p. 5
Where the paper says it

Consider as domain the real numbers R, together with the binary order relation ≤, the ternary relation R+ defined via R+(x, y, z) ⇔ x + y = z, and the unary relation R=1(x) ⇔ x = 1. Then CSP(R; ≤, R+, R=1) is polynomial time equivalent to the Linear Programming problem in feasibility form with rational input data.

p. 5
Where the paper says it

Consider as domain the real numbers R, together with the binary order relation ≤, the ternary relation R+ defined via R+(x, y, z) ⇔ x + y = z, and the unary relation R=1(x) ⇔ x = 1. Then CSP(R; ≤, R+, R=1) is polynomial time equivalent to the Linear Programming problem in feasibility form with rational input data.

p. 5
Where the paper says it

Consider as domain the real numbers R, together with the binary order relation ≤, the ternary relation R+ defined via R+(x, y, z) ⇔ x + y = z, and the unary relation R=1(x) ⇔ x = 1. Then CSP(R; ≤, R+, R=1) is polynomial time equivalent to the Linear Programming problem in feasibility form with rational input data.

p. 5
Where the paper says it

Consider as domain the real numbers R, together with the binary order relation ≤, the ternary relation R+ defined via R+(x, y, z) ⇔ x + y = z, and the unary relation R=1(x) ⇔ x = 1. Then CSP(R; ≤, R+, R=1) is polynomial time equivalent to the Linear Programming problem in feasibility form with rational input data.

p. 5
Where the paper says it

Consider as domain the real numbers R, together with the binary order relation ≤, the ternary relation R+ defined via R+(x, y, z) ⇔ x + y = z, and the unary relation R=1(x) ⇔ x = 1. Then CSP(R; ≤, R+, R=1) is polynomial time equivalent to the Linear Programming problem in feasibility form with rational input data.

p. 5
Where the paper says it

Consider as domain the real numbers R, together with the binary order relation ≤, the ternary relation R+ defined via R+(x, y, z) ⇔ x + y = z, and the unary relation R=1(x) ⇔ x = 1. Then CSP(R; ≤, R+, R=1) is polynomial time equivalent to the Linear Programming problem in feasibility form with rational input data.

p. 5
Where the paper says it

Consider as domain the real numbers R, together with the binary order relation ≤, the ternary relation R+ defined via R+(x, y, z) ⇔ x + y = z, and the unary relation R=1(x) ⇔ x = 1. Then CSP(R; ≤, R+, R=1) is polynomial time equivalent to the Linear Programming problem in feasibility form with rational input data.

05818#pg15>. The Reluplex solver for verifying Deep Neural Networks is reference [13] <ref:2306. p. 1
Where the paper says it

For the completeness results, linking the verification tasks with the theory of Constraint Satisfaction Problems turns out helpful. 1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty.

p. 1
Where the paper says it

For the completeness results, linking the verification tasks with the theory of Constraint Satisfaction Problems turns out helpful. 1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty.

p. 1
Where the paper says it

For the completeness results, linking the verification tasks with the theory of Constraint Satisfaction Problems turns out helpful. 1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty.

p. 1
Where the paper says it

For the completeness results, linking the verification tasks with the theory of Constraint Satisfaction Problems turns out helpful. 1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty.

p. 1
Where the paper says it

For the completeness results, linking the verification tasks with the theory of Constraint Satisfaction Problems turns out helpful. 1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty.

p. 1
Where the paper says it

For the completeness results, linking the verification tasks with the theory of Constraint Satisfaction Problems turns out helpful. 1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty.

p. 1
Where the paper says it

For the completeness results, linking the verification tasks with the theory of Constraint Satisfaction Problems turns out helpful. 1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty.

p. 1
Where the paper says it

For the completeness results, linking the verification tasks with the theory of Constraint Satisfaction Problems turns out helpful. 1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty.

p. 1
Where the paper says it

For the completeness results, linking the verification tasks with the theory of Constraint Satisfaction Problems turns out helpful. 1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty.

p. 1
Where the paper says it

For the completeness results, linking the verification tasks with the theory of Constraint Satisfaction Problems turns out helpful. 1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty.

p. 1
Where the paper says it

For the completeness results, linking the verification tasks with the theory of Constraint Satisfaction Problems turns out helpful. 1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty.

05818#pg15>. The survey of tractability in constraint satisfaction problems is reference [7] <ref:2306. p. 4
Where the paper says it

1 Basics on Constraint Satisfaction Problems CSP As we shall see, analyzing the complexity of the above reachability problems is closely related to suitable questions in the framework of Constraint Satisfaction Problems CSP. This is a well established area in complexity, see for example the survey [7].

p. 4
Where the paper says it

1 Basics on Constraint Satisfaction Problems CSP As we shall see, analyzing the complexity of the above reachability problems is closely related to suitable questions in the framework of Constraint Satisfaction Problems CSP. This is a well established area in complexity, see for example the survey [7].

p. 4
Where the paper says it

1 Basics on Constraint Satisfaction Problems CSP As we shall see, analyzing the complexity of the above reachability problems is closely related to suitable questions in the framework of Constraint Satisfaction Problems CSP. This is a well established area in complexity, see for example the survey [7].

p. 4
Where the paper says it

1 Basics on Constraint Satisfaction Problems CSP As we shall see, analyzing the complexity of the above reachability problems is closely related to suitable questions in the framework of Constraint Satisfaction Problems CSP. This is a well established area in complexity, see for example the survey [7].

p. 4
Where the paper says it

1 Basics on Constraint Satisfaction Problems CSP As we shall see, analyzing the complexity of the above reachability problems is closely related to suitable questions in the framework of Constraint Satisfaction Problems CSP. This is a well established area in complexity, see for example the survey [7].

p. 4
Where the paper says it

1 Basics on Constraint Satisfaction Problems CSP As we shall see, analyzing the complexity of the above reachability problems is closely related to suitable questions in the framework of Constraint Satisfaction Problems CSP. This is a well established area in complexity, see for example the survey [7].

p. 4
Where the paper says it

1 Basics on Constraint Satisfaction Problems CSP As we shall see, analyzing the complexity of the above reachability problems is closely related to suitable questions in the framework of Constraint Satisfaction Problems CSP. This is a well established area in complexity, see for example the survey [7].

p. 4
Where the paper says it

1 Basics on Constraint Satisfaction Problems CSP As we shall see, analyzing the complexity of the above reachability problems is closely related to suitable questions in the framework of Constraint Satisfaction Problems CSP. This is a well established area in complexity, see for example the survey [7].

p. 4
Where the paper says it

1 Basics on Constraint Satisfaction Problems CSP As we shall see, analyzing the complexity of the above reachability problems is closely related to suitable questions in the framework of Constraint Satisfaction Problems CSP. This is a well established area in complexity, see for example the survey [7].

p. 4
Where the paper says it

1 Basics on Constraint Satisfaction Problems CSP As we shall see, analyzing the complexity of the above reachability problems is closely related to suitable questions in the framework of Constraint Satisfaction Problems CSP. This is a well established area in complexity, see for example the survey [7].

p. 4
Where the paper says it

1 Basics on Constraint Satisfaction Problems CSP As we shall see, analyzing the complexity of the above reachability problems is closely related to suitable questions in the framework of Constraint Satisfaction Problems CSP. This is a well established area in complexity, see for example the survey [7].

05818#pg15>. The survey on deep learning architectures - A Mathematical Approach is reference [14] <ref:2306. p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

p. 1
Where the paper says it

Khan et al. [14] provide a survey of such applications, a mathematically oriented textbook concerning structural issues related to Deep Neural Networks is provided by [5].

05818#pg15>. The survey of deep neural networks for acoustic modeling in speech recognition is reference [10] <ref:2306. p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

05818#pg15>. The survey of deep learning in financial markets prediction is reference [8] <ref:2306. p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

p. 1
Where the paper says it

1 Introduction Given the huge success of utilizing (Deep) Neural Networks, (D)NN for short, in the last decade, such nets are nowadays widely used in all kind of data processing, including tasks of varying difficulty. There is a wide range of applications, the following exemplary references (mostly taken from [20]) just collect non-exclusively some areas for further reading: Image recognition [15], natural language processing [10], autonomous driving [9], applications in medicine [16], and prediction of stock markets [8], just to mention a few.

05818#pg15>. The survey of deep learning techniques for autonomous driving is reference [9] <ref:2306.05818#pg15>. The textbook concerning structural issues related to Deep Neural Networks is provided by [5] <ref:2306.05818#pg15>. The survey of safety and trustworthiness of deep neural networks is reference [19] <ref:2306.05818#pg15>. The new polynomial-time algorithm for linear programming is reference [12] <ref:2306.05818#pg15>. The Reluplex solver for verifying Deep Neural Networks is reference [13] <ref:2306.05818#pg15>. The survey of tractability in constraint satisfaction problems is reference [7] <ref:2306.05818#pg15>. The survey on deep learning architectures - A Mathematical Approach is reference [14] <ref:2306.05818#pg15>. The survey of deep neural networks for acoustic modeling in speech recognition is reference [10] <ref:2306.05818#pg15>. The survey of deep learning in financial markets prediction is reference [8] <ref:2306.05818#pg15>. The survey of deep learning techniques for autonomous driving is reference [9] <ref:2306.05818#pg15>. The textbook concerning structural issues related to Deep Neural Networks is provided by [5] <ref:2306.05818#pg15>. The survey of safety and trustworthiness of deep neural networks is reference [19] <ref:2306.05818#pg15>. The new polynomial-time algorithm for linear programming is reference [12] <ref:2306.05818#pg15>. The Reluplex solver for verifying Deep Neural Networks is reference [13] <ref:2306.05818#pg15>. The survey of tractability in constraint satisfaction problems is reference [7] <ref:2306.05818#pg15>. The survey on deep learning architectures - A Mathematical Approach is reference [14] <ref:2306.05818#pg15>. The survey of deep neural networks for acoustic modeling in speech recognition is reference [10] <ref:2306.05818#pg15>. The survey of deep learning in financial markets prediction is reference [8] <ref:2306.05818#pg15>. The survey of deep learning techniques for autonomous driving is reference [9] <ref:2306.05818#pg15>. The textbook concerning structural issues related to Deep Neural Networks is provided by [5] <ref:2306.05818#pg15>. The survey of safety and trustworthiness of deep neural networks is reference [19] <ref:2306.05818#pg15>. The new polynomial-time algorithm for linear programming is reference [12] <ref:2306.05818#pg15>. The Reluplex solver for verifying Deep Neural Networks is reference [13] <ref:2306.05818#pg15>. The survey of tractability in constraint satisfaction problems is reference [7] <ref:2306.05818#pg15>. The survey on deep learning architectures - A Mathematical Approach is reference [14] <ref:2306.05818#pg15>. The survey of deep neural networks for acoustic modeling in speech recognition is reference [10] <ref:2306.05818#pg15>. The survey of deep learning in financial markets prediction is reference [8] <ref:2306.05818#pg15>. The survey of deep learning techniques for autonomous driving is reference [9] <ref:2306.05818#pg15>. The textbook concerning structural issues related to Deep Neural Networks is provided by [5] <ref:2306.05818#pg15>. The survey of safety and trustworthiness of deep neural networks is reference [19] <ref:2306.05818#pg15>. The new polynomial-time algorithm for linear programming is reference [12] <ref:2306.05818#pg15>. The Reluplex solver for verifying Deep Neural Networks is reference [13] <ref:2306.05818#pg15>. The survey of tractability in constraint satisfaction problems is reference [7] <ref:2306.05818#pg15>. The survey on deep learning architectures - A Mathematical Approach is reference [14] <ref:2306.05818#pg15>. The survey of deep neural networks for acoustic modeling in speech recognition is reference [10] <ref:2306.05818#pg15>. The survey of deep learning in financial markets prediction is reference [8] <ref:2306.05818#pg15>. The survey of deep learning techniques for autonomous driving is reference [9] <ref:2306.05818#pg15>. The textbook concerning structural issues related to Deep Neural Networks is provided by [5] <ref:2306.05818#pg15>. The survey of safety and trustworthiness of deep neural networks is reference [19] <ref:2306.05818#pg15>. The new polynomial-time algorithm for linear programming is reference [12] <ref:2306.05818#pg15>. The Reluplex solver for verifying Deep Neural Networks is reference [13] <ref:2306.05818#pg15>. The survey of tractability in constraint satisfaction problems is reference [7] <ref:2306.05818#pg15>. The survey on deep learning architectures - A Mathematical Approach is reference [14] <ref:2306.05818#pg15>. The survey of deep neural networks for acoustic modeling in speech recognition is reference [10] <ref:2306.05818#pg15>. The survey of deep learning in financial markets prediction is reference [8] <ref:2306.05818#pg15>. The survey of deep learning techniques for autonomous driving is reference [9] <ref:2306.05818#pg15>. The textbook concerning structural issues related to Deep Neural Networks is provided by [5] <ref:2306.05818#pg15>. The survey of safety and trustworthiness of deep neural networks is reference [19] <ref:2306.05818#pg15>. The new polynomial-time algorithm for linear programming is reference [12] <ref:2306.05818#pg15>. The Reluplex solver for verifying Deep Neural Networks is reference [13] <ref:2306.05818#pg15>. The survey of tractability in constraint satisfaction problems is reference [7] <ref:2306.05818#pg15>. The survey on deep learning architectures - A Mathematical Approach is reference [14] <ref:2306.05818#pg15>. The survey of deep neural networks for acoustic modeling in speech recognition is reference [10] <ref:2306.05818#pg15>. The survey of deep learning in financial markets prediction is reference [8] <ref:2306.05818#pg15>. The survey of deep learning techniques for autonomous driving is reference [9] <ref:2306.05818#pg15>. The textbook concerning structural issues related to Deep Neural Networks is provided by [5] <ref:2306.05818#pg15>. The survey of safety and trustworthiness of deep neural networks is reference [19] <ref:2306.05818#pg15>. The new polynomial-time algorithm for linear programming is reference [12] <ref:2306.05818#pg15>. The Reluplex solver for verifying Deep Neural Networks is reference [13] <ref:2306.05818#pg15>. The survey of tractability in constraint satisfaction problems is reference [7] <ref:2306.05818#pg15>. The survey on deep learning architectures - A Mathematical Approach is reference [14] <ref:2306.05818#pg15>. The survey of deep neural networks for acoustic modeling in speech recognition is reference [10] <ref:2306.05818#pg15>. The survey of deep learning in financial markets prediction is reference [8] <ref:2306.05818#pg15>. The survey of deep learning techniques for autonomous driving is reference [9] <ref:2306.05818#pg15>. The textbook concerning structural issues related to Deep Neural Networks is provided by [5] <ref:2306.05818#pg15>. The survey of safety and trustworthiness of deep neural networks is reference [19] <ref:2306.05818#pg15>. The new polynomial-time algorithm for linear programming is reference [12] <ref:2306.05818#pg15>. The Reluplex solver for verifying Deep Neural Networks is reference [13] <ref:2306.05818#pg15>. The survey of tractability in constraint satisfaction problems is reference [7] <ref:2306.05818#pg15>. The survey on deep learning architectures - A Mathematical Approach is reference [14] <ref:2306.05818#pg15>. The survey of deep neural networks for acoustic modeling in speech recognition is reference [10] <ref:2306.05818#pg15>. The survey of deep learning in financial markets prediction is reference [8] <ref:2306.05818#pg15>. The survey of deep learning techniques for autonomous driving is reference [9] <ref:2306.05818#pg15>. The textbook concerning structural issues related to Deep Neural Networks is provided by [5] <ref:2306.05818#pg15>. The survey of safety and trustworthiness of deep neural networks is reference [19] <ref:2306.05818#pg15>. The new polynomial-time algorithm for linear programming is reference [12] <ref:2306.05818#pg15>. The Reluplex solver for verifying Deep Neural Networks is reference [13] <ref:2306.05818#pg15>. The survey of tractability in constraint satisfaction problems is reference [7] <ref:2306.05818#pg15>. The survey on deep learning architectures - A Mathematical Approach is reference [14] <ref:2306.05818#pg15>. The survey of deep neural networks for acoustic modeling in speech recognition is reference [10] <ref:2306.05818#pg15>. The survey of deep learning in financial markets prediction is reference [8] <ref:2306.05818#pg15>. The survey of deep learning techniques for autonomous driving is reference [9] <ref:2306.05818#pg15>. The textbook concerning structural issues related to Deep Neural Networks is provided by [5] <ref:2306.05818#pg15>. The survey of safety and trustworthiness of deep neural networks is reference [19] <ref:2306.05818#pg15>. The new polynomial-time algorithm for linear programming is reference [12] <ref:2306.05818#pg15>. The Reluplex solver for verifying Deep Neural Networks is reference [13] <ref:2306.05818#pg15>. The survey of tractability in constraint satisfaction problems is reference [7] <ref:2306.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Verification of reachability problems in neural networks can be solved efficiently by linking them to constraint satisfaction problems (CSP) because The fact that input and output specifications are LP instances causes, that the structures below naturally contain the relations R=1, R+, and ≤. This connection allows for a classification of a vast set of activation functions in complexity classes between P and Existential Theory of the Reals.

  2. For activation functions like ReLU, Leaky ReLU, Heaviside, and Signum, reachability problems are NP-complete because The strong version we get that NNReach(id, f) is NP-complete for f being either the absolute value, the floor or ceiling function on a bounded domain, the sign or the Heaviside function. This implies that systems using these activations cannot be verified in polynomial time unless P=NP.

  3. The Existential Theory of the Reals (ETR) hardness can be leveraged to prove that reachability problems for complex functions are at least ETR-hard, such as for f being any non-linear polynomial and ETR-hard for f any function that coincides with a non-linear polynomial on an interval. This establishes a lower bound on the computational difficulty for verifying outputs of complex networks.

  4. Network equivalence problems can be solved by reducing them to the complement of reachability problems, as NNReach(F) one-one reduces to the complement of NE(F) in linear time. This allows for checking if two different network architectures compute the same function by testing whether they do not compute the same output.

  5. Reachability problems involving a set of activation functions F containing sign or id can be solved in polynomial time for equivalence, as NE(id) is in P when sign is included in F. This means that determining if two networks using these activations are equivalent is computationally tractable.

Abstract

In this paper we investigate formal verification problems for Neural Network computations. Various reachability problems will be in the focus, such as: Given symbolic specifications of allowed inputs and outputs in form of Linear Programming instances, one question is whether valid inputs exist such that the given network computes a valid output? Does this property hold for all valid inputs? The former question's complexity has been investigated recently by Sälzer and Lange for nets using the Rectified Linear Unit and the identity function as their activation functions. We complement their achievements by showing that the problem is NP-complete for piecewise linear functions with rational coefficients that are not linear, NP-hard for almost all suitable activation functions including non-linear ones that are continuous on an interval, complete for the Existential Theory of the Reals R for every non-linear polynomial and R-hard for the exponential function and various sigmoidal functions. For the completeness results, linking the verification tasks with the theory of Constraint Satisfaction Problems turns out helpful.

Related papers