Accession Number:

ADA341808

Title:

Scalability in Neural Network Learning and Computation.

Descriptive Note:

Final/Technical 1 Jan 93-31 Dec 96

Corporate Author:

UNIVERSITY OF NORTH TEXAS DENTON DEPT OF COMPUTER SCIENCES

Personal Author(s):

Report Date:

1997-02-26

Pagination or Media Count:

11.0

Abstract:

Progress has been made in six topics in the area of computational complexity of neural networks. The loading problem for analog neural networks with only 6 nodes is NP-complete. Some foundational results on linear threshold functions with Boolean inputs have been extended to real- valued inputs. Hastad s lower bound on the dynamic range of weights for linear threshold functions has been improved slightly. Theoretical and experimental results have shown that Hopfield nets are inferior to classical sequential and parallel algorithms for the knights tour problem, a special case of the Travelling Salesperson Problem. The problem of finding stable states is PLS-complete even for some very simple and restrictive classes of Hopfield nets. We have constructed n-node planar Hopfield networks that take time 2n3 to converge sequentially, and 2n7 to converge in parallel.

Subject Categories:

  • Anatomy and Physiology
  • Statistics and Probability
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE