Related papers: Reachability Is NP-Complete Even for the Simplest Neural Networks

Reachability Is NP-Complete Even for the Simplest Neural Networks

URL: http://arxiv.org/abs/2108.13179v2
Date: Wed, 1 Sep 2021 13:19:41 GMT
Title: Reachability Is NP-Complete Even for the Simplest Neural Networks
Authors: Marco S\"alzer and Martin Lange
Abstract summary: It was recently claimed that the problem is NP-complete for general neural networks and conjunctive input/output specifications. We show that NP-hardness already holds for restricted classes of simple specifications and neural networks with just one layer.
Score: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We investigate the complexity of the reachability problem for (deep) neural networks: does it compute valid output given some valid input? It was recently claimed that the problem is NP-complete for general neural networks and conjunctive input/output specifications. We repair some flaws in the original upper and lower bound proofs. We then show that NP-hardness already holds for restricted classes of simple specifications and neural networks with just one layer, as well as neural networks with minimal requirements on the occurring parameters.

Related papers

LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
This paper studies how to introduce the popular positive linear satisfiability to neural networks. We propose the first differentiable satisfiability layer based on an extension of the classic Sinkhorn algorithm for jointly encoding multiple sets of marginal distributions.
arXiv Detail & Related papers (2024-07-18T22:05:21Z)
Verified Neural Compressed Sensing [58.98637799432153]
We develop the first (to the best of our knowledge) provably correct neural networks for a precise computational task. We show that for modest problem dimensions (up to 50), we can train neural networks that provably recover a sparse vector from linear and binarized linear measurements. We show that the complexity of the network can be adapted to the problem difficulty and solve problems where traditional compressed sensing methods are not known to provably work.
arXiv Detail & Related papers (2024-05-07T12:20:12Z)
Robustness Verifcation in Neural Networks [0.0]
We investigate formal verification problems for Neural Network computations. One question is whether there do exist valid inputs such that the network computes a valid output. We show that the problems are conquerable in a semi-linear setting.
arXiv Detail & Related papers (2024-03-20T09:34:38Z)
Extrapolation and Spectral Bias of Neural Nets with Hadamard Product: a Polynomial Net Study [55.12108376616355]
The study on NTK has been devoted to typical neural network architectures, but is incomplete for neural networks with Hadamard products (NNs-Hp) In this work, we derive the finite-width-K formulation for a special class of NNs-Hp, i.e., neural networks. We prove their equivalence to the kernel regression predictor with the associated NTK, which expands the application scope of NTK.
arXiv Detail & Related papers (2022-09-16T06:36:06Z)
Consistency of Neural Networks with Regularization [0.0]
This paper proposes the general framework of neural networks with regularization and prove its consistency. Two types of activation functions: hyperbolic function(Tanh) and rectified linear unit(ReLU) have been taken into consideration.
arXiv Detail & Related papers (2022-06-22T23:33:39Z)
On the Neural Tangent Kernel Analysis of Randomly Pruned Neural Networks [91.3755431537592]
We study how random pruning of the weights affects a neural network's neural kernel (NTK) In particular, this work establishes an equivalence of the NTKs between a fully-connected neural network and its randomly pruned version.
arXiv Detail & Related papers (2022-03-27T15:22:19Z)
Reachability In Simple Neural Networks [2.7195102129095003]
We show that NP-hardness already holds for restricted classes of simple specifications and neural networks. We give a thorough discussion and outlook of possible extensions for this direction of research on neural network verification.
arXiv Detail & Related papers (2022-03-15T14:25:44Z)
The mathematics of adversarial attacks in AI -- Why deep learning is unstable despite the existence of stable neural networks [69.33657875725747]
We prove that any training procedure based on training neural networks for classification problems with a fixed architecture will yield neural networks that are either inaccurate or unstable (if accurate) The key is that the stable and accurate neural networks must have variable dimensions depending on the input, in particular, variable dimensions is a necessary condition for stability. Our result points towards the paradox that accurate and stable neural networks exist, however, modern algorithms do not compute them.
arXiv Detail & Related papers (2021-09-13T16:19:25Z)
Training Neural Networks is ER-complete [0.7251305766151019]
Given a neural network, training data, and a threshold, it was known that it is NP-hard for the neural network such that the total error is below the threshold. We determine this fundamental problem precisely, by showing that it is ER-complete. This means that it is equivalent to deciding whether a system of ER equations and inequalities with integer coefficients and real unknowns has a solution.
arXiv Detail & Related papers (2021-02-19T08:28:37Z)
Towards Understanding Hierarchical Learning: Benefits of Neural Representations [160.33479656108926]
In this work, we demonstrate that intermediate neural representations add more flexibility to neural networks. We show that neural representation can achieve improved sample complexities compared with the raw input. Our results characterize when neural representations are beneficial, and may provide a new perspective on why depth is important in deep learning.
arXiv Detail & Related papers (2020-06-24T02:44:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.