Defining the Easy/Hard Learning
Boundary

T. X Brown
J. S. Judd

NASA Tech Briefs, NPO-19045 Jan. 1993

Abstract:
This paper will discuss a class of problems related to loading
(training) neural networks, and show that a problem is in P or NP-C
depending on the fan-in of the nodes and the class of functions that
the node can be assigned. We start by defining the problem class, and
then proceed to present and prove a series of results about this class.
In summary we show that loading becomes harder with either increasing
fan-in, increasing node functionality, or increasing topological
complexity. Interestingly, the threshold functions lie on the border
between easy and hard depending non-trivially on the other factors.