Original Contribution: Training a 3-node neural network is NP-complete

No abstract is available for this paper.

• Publication year

  1992

• Venue

  Neural Networks

• Publication date

  1992-01-05

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/S0893-6080(05)80010-3
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Cryptographic limitations on learning Boolean formulae and finite automata

  1994cited by this paper
• Neural network design and the complexity of learning

  1990cited by this paper
• Crytographic limitations on learning Boolean formulae and finite automata

  1989cited by this paper
• An O(n0.4)-approximation algorithm for 3-coloring

  1989cited by this paper
• What Size Net Gives Valid Generalization?

  1989cited by this paper
• Sigmoids Distinguish More Efficiently Than Heavisides

  1989cited by this paper
• Sigmoids distinguish better than Heavisides

  1989cited by this paper
• On the complexity of polyhedral separability

  1988cited by this paper
• Learning in threshold networks

  1988cited by this paper
• Scaling Relationships in Back-propagation Learning

  1988cited by this paper
• On the learnability of Boolean formulae

  1987cited by this paper
• Parallel Networks that Learn to Pronounce English Text

  1987cited by this paper
• Learning internal representations by error propagation

  1986cited by this paper
• Improving the performance guarantee for approximate graph coloring

  1983cited by this paper
• Computers and Intractability: A Guide to the Theory of NP-Completeness

  1979cited by this paper

• The Fusion Mechanism and Prospective Application of Physics-Informed Machine Learning in Bridge Lifecycle Health Monitoring

  2026cites this paper
• Why ReLU? A Bit-Model Dichotomy for Deep Network Training

  2026cites this paper
• P3DE: A novel integration of deep ensemble learning and parameter-less optimization for superior breast cancer biomarker discovery

  2026cites this paper
• Cryptanalytic Extraction of Convolutional Neural Networks

  2026cites this paper
• Deep asymptotic expansion method for solving singularly perturbed time-dependent reaction-advection-diffusion equations

  2025influential citation
• A Distributional-Lifting Theorem for PAC Learning

  2025cites this paper
• Efficient identification of wide shallow neural networks with biases

  2025cites this paper
• Physics-informed machine learning in geotechnical engineering: a direction paper

  2025cites this paper
• Foundations of Artificial Intelligence Frameworks: Notion and Limits of AGI

  2025cites this paper
• Wormhole Dynamics in Deep Neural Networks

  2025cites this paper
• Clustering of Geographical Segments for Predictive Quality of Service of Connected Vehicles

  2025cites this paper
• Implementing Hybrid Quantum Neural Networks for Accurate Wildfire Detection

  2025cites this paper
• Fractional conservative variational physics-informed neural networks: A method for solving Stokes equations with time Caputo derivative

  2025cites this paper
• Monotone and Separable Set Functions: Characterizations and Neural Models

  2025cites this paper
• Influence of IQT on research in ICT, part 2

  2025cites this paper
• Probabilistically robust counterfactual explanations under model changes

  2025cites this paper
• Take Goodhart Seriously: Principled Limit on General-Purpose AI Optimization

  2025cites this paper
• Training Cross-Morphology Embodied AI Agents: From Practical Challenges to Theoretical Foundations

  2025cites this paper
• Multiplication Is Hard: A Review Of Techniques Aiming To Parallelize Matrix Operations To Accelerate Crypto-ML Frameworks 

  2025cites this paper
• SwarmCNN: An efficient method for CNN hyperparameter optimization using PSO and ABC metaheuristic algorithms

  2025cites this paper
• Convex-Concave Programming: An Effective Alternative for Optimizing Shallow Neural Networks

  2025cites this paper
• Extracting Some Layers of Deep Neural Networks in the Hard-Label Setting

  2025cites this paper
• Train on classical, deploy on quantum: scaling generative quantum machine learning to a thousand qubits

  2025cites this paper
• Enabling Local Neural Operators to perform Equation-Free System-Level Analysis

  2025cites this paper
• Physics-informed extreme learning machine for rapid form-finding of frame-supported lightweight tensile membrane structures

  2025cites this paper
• The Finite Element Neural Network Method: One Dimensional Study

  2025cites this paper
• Undecidable problems associated with variational quantum algorithms

  2025cites this paper
• Why Machine Learning Needs Theoretical Guidance to Support Future Theory Building

  2025cites this paper
• An Additively Preconditioned Trust Region Strategy for Machine Learning

  2025cites this paper
• A Hybrid Neural Network - Polynomial Series Scheme for Learning Invariant Manifolds of Discrete Dynamical Systems

  2025cites this paper
• DEVELOPMENT OF HYBRID QUANTUM-CLASSICAL MODELS FOR COMPUTER VISION

  2025cites this paper
• An experimental comparative study of backpropagation and alternatives for training binary neural networks for image classification

  2024cites this paper
• Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility Through Quantization

  2024cites this paper
• Towards Collaborative Edge Intelligence: Blockchain-Based Data Valuation and Scheduling for Improved Quality of Service

  2024cites this paper
• Optimal robust Memorization with ReLU Neural Networks

  2024cites this paper
• Exploring Loss Landscapes through the Lens of Spin Glass Theory

  2024cites this paper
• Computational Complexity of Neural Network Linear Layer Inference Optimizations

  2024cites this paper
• Learning of Multi-valued Multithreshold Neural Units

  2024cites this paper
• Hardness of Learning Neural Networks under the Manifold Hypothesis

  2024cites this paper
• Limits of Transformer Language Models on Learning to Compose Algorithms

  2024cites this paper
• Solution space and storage capacity of fully connected two-layer neural networks with generic activation functions

  2024cites this paper
• Chebyshev Spectral Neural Networks for Solving Partial Differential Equations

  2024cites this paper
• MESA: Cooperative Meta-Exploration in Multi-Agent Learning through Exploiting State-Action Space Structure

  2024cites this paper
• Multithreshold Neural Units for Multiclass Classification

  2024cites this paper
• Oracle-Efficient Differentially Private Learning with Public Data

  2024cites this paper
• Nearest Neighbor Complexity and Boolean Circuits

  2024cites this paper
• A First Step Towards Runtime Analysis of Evolutionary Neural Architecture Search

  2024cites this paper
• Optimal feature rescaling in machine learning based on neural networks

  2024cites this paper
• GFLASSO-LR: Logistic Regression with Generalized Fused LASSO for Gene Selection in High-Dimensional Cancer Classification

  2024cites this paper
• On the Empirical Complexity of Reasoning and Planning in LLMs

  2024cites this paper
• Machine learning for modeling human decisions.

  2024cites this paper
• Physics-Informed neural network solver for numerical analysis in geoengineering

  2024cites this paper
• Limits of Transformer Language Models on Learning Algorithmic Compositions

  2024cites this paper
• Inter-layer Recurrent Neural Networks Learning Algorithms

  2024cites this paper
• CRONOS: Enhancing Deep Learning with Scalable GPU Accelerated Convex Neural Networks

  2024cites this paper
• Hard-Label Cryptanalytic Extraction of Neural Network Models

  2024cites this paper
• Polynomial Time Cryptanalytic Extraction of Deep Neural Networks in the Hard-Label Setting

  2024cites this paper
• Absence of Closed-Form Descriptions for Gradient Flow in Two-Layer Narrow Networks

  2024cites this paper
• An Interpretable Generalization Mechanism for Accurately Detecting Anomaly and Identifying Networking Intrusion Techniques

  2024cites this paper
• Challenges and Emerging Issues for Generative AI and Hyper Intelligence

  2024cites this paper
• A hybrid intelligent optimization algorithm to select discriminative genes from large-scale medical data

  2024cites this paper
• Evolutionary feature selection on high dimensional data using a search space reduction approach

  2023cites this paper
• Random Linear Projections Loss for Hyperplane-Based Optimization in Neural Networks

  2023cites this paper
• Hidden Minima in Two-Layer ReLU Networks

  2023cites this paper
• Parallel Trust-Region Approaches in Neural Network Training: Beyond Traditional Methods

  2023cites this paper
• An improved binary dandelion algorithm using sine cosine operator and restart strategy for feature selection

  2023cites this paper
• All Critical Gradient Descent

  2023cites this paper
• Applying statistical learning theory to deep learning

  2023cites this paper
• From data to insight, enhancing structural health monitoring using physics-informed machine learning and advanced data collection methods

  2023cites this paper
• Deep Learning Algorithm for Detecting and Analyzing Criminal Activity

  2023cites this paper
• “All” Critical Gradient Descent Solutions Are Optimal & Small Running time

  2023influential citation
• 3-Layer Neural Network Classifier With the Heterogeneous Hidden Layers

  2023cites this paper
• Meta Co-Training: Two Views are Better than One

  2023cites this paper
• Gradient is All You Need? How Consensus-Based Optimization can be Interpreted as a Stochastic Relaxation of Gradient Descent

  2023cites this paper
• Are alternatives to backpropagation useful for training Binary Neural Networks? An experimental study in image classification

  2023cites this paper
• No Wrong Turns: The Simple Geometry Of Neural Networks Optimization Paths

  2023cites this paper
• Hybrid 4-Layer Bithreshold Neural Network for Multiclass Classification

  2023cites this paper
• Convolution Hierarchical Deep-learning Neural Networks (C-HiDeNN): finite elements, isogeometric analysis, tensor decomposition, and beyond

  2023cites this paper
• Black Holes and the loss landscape in machine learning

  2023cites this paper
• A Survey on Solving and Discovering Differential Equations Using Deep Neural Networks

  2023cites this paper
• Training neural networks from an ergodic perspective

  2023cites this paper
• Stock price prediction using a novel approach in Gaussian mixture model-hidden Markov model

  2023cites this paper
• Theoretical bounds of generalization error for generalized extreme learning machine and random vector functional link network

  2023cites this paper
• When Deep Learning Meets Polyhedral Theory: A Survey

  2023cites this paper
• Polynomial Time Cryptanalytic Extraction of Neural Network Models

  2023cites this paper
• Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding

  2023cites this paper
• Convex Dual Theory Analysis of Two-Layer Convolutional Neural Networks With Soft-Thresholding

  2023cites this paper
• Gradient free stochastic training of ANNs, with local approximation in partitions

  2023cites this paper
• Blockchain-based Data Quality Assessment to Improve Distributed Machine Learning

  2023cites this paper
• Complex Critical Points of Deep Linear Neural Networks

  2023cites this paper
• Who Should Predict? Exact Algorithms For Learning to Defer to Humans

  2023cites this paper
• Training Neural Networks is NP-Hard in Fixed Dimension

  2023cites this paper
• SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics

  2023cites this paper
• First Steps Towards a Runtime Analysis of Neuroevolution

  2023cites this paper
• On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrization

  2022cites this paper
• Judicial Review: Democratic Institution or Undemocratic Policy Judicial Review: Democratic Institution or Undemocratic Policy Tool, An Historical Perspective Tool, An Historical Perspective

  2022cites this paper
• Finite Sample Identification of Wide Shallow Neural Networks with Biases

  2022cites this paper
• Hybrid Quantum-Classical Neural Networks

  2022cites this paper
• A game-theoretic perspective of deep neural networks

  2022cites this paper
• Diabetic retinopathy prediction using Progressive Ablation Feature Selection: A comprehensive classifier evaluation

  2022cites this paper