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

Keywords

Simple (philosophy), Computer science, Node (physics), Artificial neural network, Set (abstract data type)

References

• Scaling Relationships in Back-propagation LearningGerald Tesauro, Bob Janssens — 1988
• Improving the performance guarantee for approximate graph coloringAvi Wigderson — 1983
• Computers and Intractability: A Guide to the Theory of NP-CompletenessM. R. Garey, David S. Johnson — 1979
• Sigmoids Distinguish More Efficiently Than HeavisidesEduardo D. Sontag — 1989
• An O(n0.4)-approximation algorithm for 3-coloringAvrim Blum — 1989
• Learning in threshold networksP. Raghavan — 1988
• On the learnability of Boolean formulaeMichael Kearns, M. Li, Leonard Pitt — 1987
• On the complexity of polyhedral separabilityNimrod Megiddo — 1988
• Neural network design and the complexity of learningJudd, Stephen J. — 1990
• Cryptographic limitations on learning Boolean formulae and finite automataMichael Kearns, Leslie G. Valiant — 1994
• Crytographic limitations on learning Boolean formulae and finite automataMichael Kearns, Leslie G. Valiant — 1989
• What Size Net Gives Valid Generalization?Eric B. Baum, David Haussler — 1989
• Learning internal representations by error propagationDavid E. Rumelhart, Geoffrey E. Hinton, Ronald J. Williams — 1986
• Parallel Networks that Learn to Pronounce English TextTerrence J. Sejnowski — 1987
• Neural network design and the complexity of learningV.D. Sánchez A. — 1991
• Neural network design and the complexity of learning1992
• Sigmoids distinguish better than HeavisidesEduardo Sontag — 1989

Cited by

• A Mathematical Solution to a Network Designing ProblemHans Peter Grüner — 1995
• Estimation of Discriminative Feature Subset Using Community ModularityGuodong Zhao, Sanming Liu — 2016
• Useful Feature Subsets and Rough Set ReductsRon Kohavi, Brian Frasca — 1994
• Cryptographic Hardness Results for Learning Intersections of HalfspacesAdam R. Klivans, Alexander A. Sherstov — 2006
• A framework to deal with interference in connectionist systemsVicente Ruiz de Angulo, Carme Torras — 2000
• Neural network design and the complexity of learning, by J. Stephen Judd. Cambridge, MA: MIT Press, 1990Vasant Honavar — 1992
• Some Topics in Neural Networks and ControlEduardo D. Sontag — 1993
• Learning and representation: Tensions at the interfaceSteven José Hanson — 1990
• Presenting and Analyzing the Results of AI Experiments: Data Averaging and Data SnoopingC. Lee Giles, Steve Lawrence — 1997
• The neural network loading problem is undecidableHerbert Wiklicky — 1994
• Induction of Oblique Decision TreesDavid G. Heath, Simon Kasif, Steven L. Salzberg — 1993
• Learning Efficiently with Neural Networks: A Theoretical Comparison between Structured and Flat RepresentationsMarco Gori, Paolo Frasconi, Alessandro Sperduti — 2000
• Arabic Text Categorization System - Using Ant Colony Optimization-Based Feature SelectionAbdelwadood Mesleh, Ghassan Kanaan — 2008
• Some Notes on Computational Learing TheoryAlberto Bertoni, Paola Campadelli, Giancarlo Mauri — 1991
• Discovering hierarchical decision rules with evolutive algorithms in supervised learningJosé C. Riquelme, Jesús S. Aguilar–Ruiz, Miguel Toro — 2000
• Neural networks and multimedia datasets: estimating the size of neural networks for achieving high classification accuracyGeorgios Lappas — 2009
• Learning recursive data is intractableBarbara Hammer — 1997
• Neural network learning of nonstationary processesVicente Ruiz de Angulo, Carme Torras — 1998
• NET PROPHET : McCulloch and developments from his neural net modelP. Cull — 1996
• Constructivist neural network models of cognitive developmentGert Westermann — 2000

Related papers

• Training Systems Concept for the Armored Family of Vehicles with Consideration of the Roles of Embedded Training and Stand-Alone Training DevicesJ. T. Roth, W. Peter Cherry, H. C. Strasel — 1988
• The [0-Simple] Simple Subsemigroups of Nonnegative MatricesQian Shuang-ping — 2000
• Fundamental relations in simple and 0-simple semihypergroups of small sizeDario Fasino, Domenico Freni — 2012
• Effects of Training Input on Training Performance of Airline Service Training - Focused on Mediating Role of Training Process -Hye-Young Park, Sunjoo Hur — 2012
• Book Review: IV. Pastorial — Practical Studies: Simple Sermons for Times like These, Simple Sermons on Evangelistic Themes, Simple Talks for Christian Workers, Simple Sermons on Prophetic Themes, Simple Sermons about Jesus Christ, Simple Sermons on Heaven, Hell, and Judgment, Simple Sermons on the Ten Commandments, Simple Sermons for a Sinful Age, Simple Sermons on the Seven Churches of RevelationJames W. Cox — 1975
• Models of intermodal node representationGian Carla Cassone, Domenico Gattuso — 2010