On the power of neural networks for solving hard problems

DOI10.1016/0885-064X(90)90001-TzbMath0694.68028MaRDI QIDQ909457

Jehoshua Bruck, Joseph W. Goodman

Publication date: 1990

Published in: Journal of Complexity (Search for Journal in Brave)

zbMATH Keywords

neural networkNP-hard problemspolynomial size network

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Neural networks and heuristic search, Metaheuristics: A bibliography, Intractability and approximation of optimization theories of cognition, Heuristics from Nature for Hard Combinatorial Optimization Problems, Finding approximate solutions to NP-hard problems by neural networks is hard, On the performance guarantee of neural networks for NP-hard optimization problems, Neural network methods in combinatorial optimization, Nonparametric graded data processing with back-error propagation networks, Neural networks as systems for recognizing patterns, A neural network for the minimum set covering problem

Cites Work

• Unnamed Item
• Unnamed Item
• ``Neural computation of decisions in optimization problems
• A study on neural networks
• A generalized convergence theorem for neural networks
• Minimum cuts and related problems
• On the Complexity of Local Search for the Traveling Salesman Problem
• Neural networks and physical systems with emergent collective computational abilities.